牛吃饭排队喜欢靠近朋友。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。