题目描述

原题来自：USACO 2005 Dec. Gold

FJ 有 $\red N$ 头奶牛 ($\red {2≤N≤1000}$)，编号为 $\red {1…N}$。奶牛们将按照编号顺序排成一列队伍（可能有多头奶牛在同一位置上）。

换句话说，假设 $\red i$ 号奶牛位于 $\red{P_i}$​，则 $\red{P_1​≤P_2​≤…≤P_N​}$。

有些奶牛是好基友，它们希望彼此之间的距离小于等于某个数。

有些奶牛是情敌，它们希望彼此之间的距离大于等于某个数。

给出 $\red{M_L}$​ 对好基友的编号，以及它们希望彼此之间的距离小于等于多少；又给出 $\red{M_D}$​ 对情敌的编号，以及它们希望彼此之间的距离大于等于多少 ($\red{1≤M_L , M_D​≤10^4}$)。

请计算：如果满足上述所有条件，$\red 1$ 号奶牛和 $\red N$ 号奶牛之间的距离（$\red{P_N​−P_1}$​）最大为多少。

输入格式

第一行：三个整数 $\red{N,M_L,M_D}$​，用空格分隔。

第 $\red{P_2…M_L+1}$ 行：每行三个整数 $\red{A,B,D}$，用空格分隔，表示 $\red{P_B​−P_A​≤D}$。

第 $\red{M_L+2…M_L+M_D+1}$ 行：每行三个整数 $\red{A,B,D}$，用空格分隔，表示 $\red{P_B−P_A≥D}$。

保证 $\red{1≤A<B≤N}$, $\red{1≤D≤10^6}$。

输出格式

一行，一个整数。

如果没有合法方案，输出 $\red{-1}$.

如果有合法方案，但 $\red 1$ 号奶牛可以与 $\red N$ 号奶牛相距无穷远，输出 $\red{-2}$.

否则，输出 $\red 1$ 号奶牛与 $\red N$ 号奶牛间的最大距离。

样例

输入样例

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

输出样例

27

提示

对于全部数据，$\red {2≤N≤1000,1≤M_L,M_D≤10^4,1≤L,D≤10^6}$。

这四头牛分别位于 $\red{0,7,10,27}$。