牛餵食排隊喜歡靠近朋友。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。