Mucche vogliono amici vicino in coda. John ha $N$ ($2\le N\le1{,}000$), numeri $1..N$, su retta in ordine numerico. Spingendosi più mucche possono condividere stessa posizione e coordinata.

Le mucche amiche vogliono essere separate al più da una certa distanza; le nemiche almeno da una certa distanza. $ML$ ($1\le ML\le10{,}000$) vincoli amici danno massimo, poi $MD$ ($1\le MD\le10{,}000$) nemici minimo.

Trovate se possibile massima distanza 1 a $N$ rispettando vincoli.

Input

Riga 1: interi $N,ML,MD$ per spazi.

Righe $2..ML+1$: positivi $A,B,D$ per spazi, $1\le A<B\le N$, distanza al più $D$, $1\le D\le1{,}000{,}000$.

Righe $ML+2..ML+MD+1$: positivi $A,B,D$ per spazi, $1\le A<B\le N$, distanza almeno $D$, $1\le D\le1{,}000{,}000$.

Output

Riga 1: intero, impossibile $-1$, 1 e $N$ arbitrariamente lontane $-2$, altrimenti massimo.

Esempi

Input 1

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

Output 1

27

Nota

Nota

Spiegazione dell’esempio:

4 mucche, 1 e 3 massimo 10, 2 e 4 massimo 20, nemiche 2 e 3 minimo 3.

Coordinate migliori: 1 a 0, 2 a 7, 3 a 10, 4 a 27.