暂无测试数据。

题目描述

原题来自：USACO 2005 Dec. Gold

FJ 有 \(N\) 头奶牛 \((2\le N\le 1000)\)，编号为 \(1\ldots N\)。奶牛们将按照编号顺序排成一列队伍（可能有多头奶牛在同一位置上）。换句话说，假设 \(i\) 号奶牛位于 \(P_{\!\;i}\)，则 \(P_{\,1}\le P_{\,2}\le \ldots\le P_{\!\;N}\)。

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

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

请计算：如果满足上述所有条件，\(1\) 号奶牛和 \(N\) 号奶牛之间的距离（\(P_{\!\;N}-P_{\,1}\)）最大为多少。

输入格式

第一行：三个整数 \(N, M_L, M_D\)，用空格分隔。

第 \(2\dots M_L+1\) 行：每行三个整数 \(A, B, D\)，用空格分隔，表示 \(P_A-P_B\le D\)。

第 \(M_L+2\dots M_L+M_D+1\) 行：每行三个整数 \(A, B, D\)，用空格分隔，表示 \(P_A-P_B\ge D\)。

保证 \(1\le A<B\le N,\) \(1\le D\le 10^6\).

输出格式

一行，一个整数。如果没有合法方案，输出 \(\texttt{-1}\). 如果有合法方案，但 \(1\) 号奶牛可以与 \(N\) 号奶牛相距无穷远，输出 \(\texttt{-2}\). 否则，输出 \(1\) 号奶牛与 \(N\) 号奶牛间的最大距离。

样例数据

样例输入

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

样例输出

27

样例说明

这四头牛分别位于 \(0,7,10,27\)。

限制与提示

对于全部数据，\(2\le N\le 1000,1\le M_L,M_D\le 10^4,1\le L,D\le 10^6\)。