פרות רוצות חברים קרוב בתור למזון. ל־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.