题目描述
当排队等候喂食时,奶牛喜欢和它们的朋友站得靠近些。FJ有N(2<=N<=1000)头奶牛,编号从1到N,沿一条直线站着等候喂食。奶牛排在队伍中的顺序和它们的编号是相同的。因为奶牛相当苗条,所以可能有两头或者更多奶牛站在同一位置上。即使说,如果我们想象奶牛是站在一条数轴上的话,允许有两头或更多奶牛拥有相同的横坐标。
一些奶牛相互间存有好感,它们希望两者之间的距离不超过一个给定的数L。另一方面,一些奶牛相互间非常反感,它们希望两者间的距离不小于一个给定的数D。给出ML条关于两头奶牛间有好感的描述,再给出MD条关于两头奶牛间存有反感的描述。(1<=ML,MD<=10000,1<=L,D<=1000000)
你的工作是:如果不存在满足要求的方案,输出-1;如果1号奶牛和N号奶牛间的距离可以任意大,输出-2;否则,计算出在满足所有要求的情况下,1号奶牛和N号奶牛间可能的最大距离。
输入格式
第一行三个整数:N,X和Y。(2<=N<=1000, 1<=X,Y<=10000) N表示N头牛。X表示有X对牛关系好,距离不能超过某个值,Y表示有Y对牛关系不好,距离不能低于某个值。
接下来X行:每行3个整数A,B,D。表示第A头牛和第B头牛的距离不能超过D。 接下来Y行:每行3个整数A,B,D。表示第A头牛和第B头牛的距离不能低过D。 1 <= A < B <= N (1 <= D <= 1,000,000)
输出格式
一个整数,表示第1头牛到第N头牛的最长距离。 如果这n头无法排成队伍,则输出-1,如果牛[1]和牛[n]的距离可以无限远,则输出-2。
样例数据
input
4 2 1
1 3 10
2 4 20
2 3 3
output
27
数据规模与约定
poj 3169
时间限制:$1 text {s}$
空间限制:$256 text {MB}$


