Les vaches aiment leurs amis près d’elles en file. John en a $N$ ($2\le N\le1{,}000$), numéros $1..N$, sur une droite en ordre numérique. Plusieurs peuvent se pousser au même endroit, donc même coordonnée.

Amis veulent distance plafonnée, ennemis un minimum. $ML$ ($1\le ML\le10{,}000$) contraintes d’amitié donnent maximum, puis $MD$ ($1\le MD\le10{,}000$) d’inimitié donnent minimum.

Calculez si possible distance maximale entre 1 et $N$ satisfaisant les contraintes.

Entrée

Ligne 1 : entiers $N,ML,MD$ séparés par espaces.

Lignes $2..ML+1$ : positifs $A,B,D$ par espaces, $1\le A<B\le N$, distance au plus $D$, $1\le D\le1{,}000{,}000$.

Lignes $ML+2..ML+MD+1$ : positifs $A,B,D$ par espaces, $1\le A<B\le N$, distance au moins $D$, $1\le D\le1{,}000{,}000$.

Sortie

Ligne 1 : entier, impossible $-1$, distance arbitrairement grande entre 1 et $N$ : $-2$, sinon maximum.

Exemples

Entrée 1

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

Sortie 1

27

Remarque

Remarque

Explication de l’exemple :

4 vaches, 1 et 3 au plus 10, 2 et 4 au plus 20, ennemies 2 et 3 au moins 3.

Meilleures coordonnées : 1 à 0, 2 à 7, 3 à 10, 4 à 27.