【CZYZOI 2017.04.16 C】 排队

内存限制: 128 MiB 时间限制: 1000 ms
标准输入输出

题目描述

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

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

你的任务是计算在满足以上条件的前提下,帮助Czy计算出编号为 11 和编号为 NN 的妹纸之间距离的最大可能值。

输入格式

第一行有 33 个整数,每两个整数之间用一个空格隔开,依次表示 n,MLn,MLMDMD

此后 MLML 行,每行包含三个用空格分开的整数 A,BA,BDD ,其中 A,BA,B 满足 1ABN1\le A\le B\le N 。表示编号为 AABB 的妹纸之间的距离至多为 DD

此后 MDMD 行,每行包含三个用空格分开的整数 A,BA,BDD ,其中 A,BA,B 满足 1ABN1\le A\le B\le N 。表示编号为 AABB 的妹纸之间的距离至少为 DD

输出格式

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

样例

输入样例

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

输出样例

27

数据范围与提示

对于 40%40\% 的数据,N100N\le100

对于 100%100\% 的数据,N1000N\le1000ML,MD10000ML,MD\le10000D1000000D\le1000000