Problem1090--「一本通 3.4 练习 2」排队布局

1090: 「一本通 3.4 练习 2」排队布局

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 0  Solved: 0
Submit Status Web Board

Creator:

Description

原题来自:USACO 2005 Dec. Gold

当排队等候喂食时,奶牛喜欢和它们的朋友站得靠近些。FJ 有 NNN 头奶牛,编号从 111NNN,沿一条直线站着等候喂食。奶牛排在队伍中的顺序和它们的编号是相同的。因为奶牛相当苗条,所以可能有两头或者更多奶牛站在同一位置上。即使说,如果我们想象奶牛是站在一条数轴上的话,允许有两头或更多奶牛拥有相同的横坐标。一些奶牛相互间存有好感,它们希望两者之间的距离不超过一个给定的数 LLL。另一方面,一些奶牛相互间非常反感,它们希望两者间的距离不小于一个给定的数 DDD

给出 MLM_LML 条关于两头奶牛间有好感的描述,再给出 MDM_DMD 条关于两头奶牛间存有反感的描述。你的工作是:如果不存在满足要求的方案,输出 −1-11;如果 111 号奶牛和 NNN 号奶牛间的距离可以任意大,输出 −2-22;否则,计算出在满足所有要求的情况下,111 号奶牛和 NNN 号奶牛间可能的最大距离。


Input

第一行三个整数 N,ML,MDN,M_L,M_DN,ML,MD

接下来 MLM_LML 行,每行三个正整数 A,B,DA,B,DA,B,D,表示奶牛 AAA 和奶牛 BBB 至多相隔 DDD 的距离;

接下来 MDM_DMD 行,每行三个正整数 A,B,DA,B,DA,B,D,表示奶牛 AAA 和奶牛 BBB 至少相隔 DDD 的距离。


Output

如果不存在满足要求的方案,输出 −1-11;如果 111 号奶牛和 NNN 号奶牛间的距离可以任意大,输出 −2-22;否则,计算出在满足所有要求的情况下,111 号奶牛和 NNN 号奶牛间可能的最大距离。


Sample Input

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

Sample Output

27

HINT

对于全部数据,2≤N≤1000,1≤ML,MD≤104,1≤L,D≤1062\le N\le 1000,1\le M_L,M_D\le 10^4,1\le L,D\le 10^62N1000,1ML,MD104,1L,D106


Source/Category


Submit Status