#180. 「一本通 3.4 练习 2」[ USACO ] Layout 布局

「一本通 3.4 练习 2」[ USACO ] Layout 布局

题目描述

原题来自:USACO 2005 Dec. Gold

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

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

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

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

输入格式

第一行:三个整数 N,ML,MDN, M_L, M_D,用空格分隔。
2ML+12\dots M_L+1 行:每行三个整数 A,B,DA, B, D,用空格分隔,表示 PBPADP_B-P_A\le D
ML+2ML+MD+1M_L+2\dots M_L+M_D+1 行:每行三个整数 A,B,DA, B, D,用空格分隔,表示 PBPADP_B-P_A\ge D
保证 1A<BN,1\le A<B\le N, 1D1061\le D\le 10^6

输出格式

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

样例

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

这四头牛分别位于 0,7,10,270,7,10,27

数据范围与提示

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