排队

排队

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

刘宝宝喜欢将他的妹子们排成一队。假设他拥有N只妹纸,编号为1至N。刘宝宝让他们站成一行,等待自己来派送营养餐。这些妹纸按照编号大小排列,并且由于它们都很想早点吃饭,于是就很可能出现多只妹纸挤在同一位置的情况(也就是说,如果我们认为妹纸位于数轴上,那么多只妹纸的位置坐标可能相同)。

因为众所周知的原因,某些妹纸之间互相喜欢,他们希望互相之间的距离至多为一个定值。但某些妹纸之间互相厌恶,他们希望互相之间的距离至少为一个定值。现在给定ML个互相喜爱的妹纸对以及他们之间距离的最大值,MD个互相厌恶的妹纸对以及他们之间距离的最小值。

你的任务是计算在满足以上条件的前提下,帮助刘宝宝计算出编号为1和编号为N的妹纸之间距离

Format

Input

第一行有 3 个整数,每两个整数之间用一个空格隔开,依次表示 n,ML和DL ;

此后ML行,每行包含三个用空格分开的整数A,B和D,其中A,B满足1<=A<=B<=N。表示编号为A和B的妹纸之间的距离至多为D。

此后MD行,每行包含三个用空格分开的整数A,B和D,其中A,B满足1<=A<=B<=N。表示编号为A和B的妹纸之间的距离至少为D。

Output

输出文件仅包含一个整数。如果不存在任何合法的排队方式,就输出-1。如果编号1和编号N的妹纸间距离可以任意,就输出-2 。否则输出他们之间的最大可能距离。

Sample 1

Input

4 2 1

1 3 10

2 4 20

2 3 3

Output

27

Limitation

对于40%的数据,N<=100;

对于100%的数据,N<=1000;ML,MN<=10000;D<=1000000。

水题盛宴

未参加
状态
已结束
规则
OI
题目
3
开始于
2017-10-31 18:45
结束于
2017-10-31 21:45
持续时间
3.0 小时
主持人
参赛人数
13