Коровы любят друзей рядом в очереди к корму. У John $N$ ($2\le N\le1{,}000$), номера $1..N$, на прямой в порядке номеров. Из-за толкотни несколько могут иметь одну координату.

Друзья хотят расстояние не больше предела, враги не меньше. $ML$ ($1\le ML\le10{,}000$) ограничений дружбы задают максимум, затем $MD$ ($1\le MD\le10{,}000$) вражды задают минимум.

Найдите, если возможно, максимальное расстояние 1 и $N$ при всех ограничениях.

Входные данные

Строка 1: целые $N,ML,MD$ через пробел.

Строки $2..ML+1$: положительные $A,B,D$ через пробел, $1\le A<B\le N$, расстояние не больше $D$, $1\le D\le1{,}000{,}000$.

Строки $ML+2..ML+MD+1$: положительные $A,B,D$ через пробел, $1\le A<B\le N$, расстояние не меньше $D$, $1\le D\le1{,}000{,}000$.

Выходные данные

Строка 1: целое, невозможность $-1$, неограниченная дальность 1 и $N$ — $-2$, иначе максимальная дистанция.

Примеры

Входные данные 1

4 2 1
1 3 10
2 4 20
2 3 3

Выходные данные 1

27

Примечание

Примечание

Объяснение примера:

4 коровы: 1 и 3 не более 10, 2 и 4 не более 20, враги 2 и 3 не менее 3.

Лучшие координаты: 1 в 0, 2 в 7, 3 в 10, 4 в 27.