牛は餌の列で友達に近づきたいです。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。