Krowy chcą blisko przyjaciół w kolejce. John ma $N$ ($2\le N\le1{,}000$), numery $1..N$, na prostej w kolejności numerów. Przez popychanie kilka może dzielić pozycję i współrzędną.

Zaprzyjaźnione krowy chcą być oddalone najwyżej o pewną odległość, a wrogie co najmniej o pewną odległość. $ML$ ($1\le ML\le10{,}000$) ograniczeń przyjaciół daje maksimum, potem $MD$ ($1\le MD\le10{,}000$) wrogów minimum.

Znajdź, jeśli możliwe, maksymalną odległość 1 i $N$ zgodną z ograniczeniami.

Wejście

Wiersz 1: całkowite $N,ML,MD$ spacjami.

Wiersze $2..ML+1$: dodatnie $A,B,D$ spacjami, $1\le A<B\le N$, odległość najwyżej $D$, $1\le D\le1{,}000{,}000$.

Wiersze $ML+2..ML+MD+1$: dodatnie $A,B,D$ spacjami, $1\le A<B\le N$, odległość co najmniej $D$, $1\le D\le1{,}000{,}000$.

Wyjście

Wiersz 1: całkowite, niemożliwe $-1$, 1 i $N$ dowolnie daleko $-2$, inaczej maksimum.

Przykład

Wejście 1

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

Wyjście 1

27

Uwagi

Uwagi

Wyjaśnienie przykładu:

4 krowy, 1 i 3 najwyżej 10, 2 i 4 najwyżej 20, wrogowie 2 i 3 co najmniej 3.

Najlepsze współrzędne: 1 w 0, 2 w 7, 3 w 10, 4 w 27.