Vacas quieren amigos cerca en cola de comida. John tiene $N$ ($2\le N\le1{,}000$), números $1..N$, en recta en orden numérico. Varias pueden empujar hasta misma posición, compartiendo coordenada.

Las vacas amigas quieren estar a no más de cierta distancia; las enemigas, a no menos de cierta distancia. $ML$ ($1\le ML\le10{,}000$) restricciones amigas dan máximo, luego $MD$ ($1\le MD\le10{,}000$) enemigas mínimo.

Halle, si posible, máxima distancia 1 a $N$ cumpliendo restricciones.

Entrada

Línea 1: enteros $N,ML,MD$ por espacios.

Líneas $2..ML+1$: positivos $A,B,D$ por espacios, $1\le A<B\le N$, distancia como máximo $D$, $1\le D\le1{,}000{,}000$.

Líneas $ML+2..ML+MD+1$: positivos $A,B,D$ por espacios, $1\le A<B\le N$, distancia al menos $D$, $1\le D\le1{,}000{,}000$.

Salida

Línea 1: entero, imposible $-1$, 1 y $N$ arbitrariamente lejos $-2$, si no máxima distancia.

Ejemplos

Entrada 1

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

Salida 1

27

Nota

Nota

Explicación del ejemplo:

4 vacas, 1 y 3 máximo 10, 2 y 4 máximo 20, enemigas 2 y 3 mínimo 3.

Mejores coordenadas: 1 en 0, 2 en 7, 3 en 10, 4 en 27.