题目描述

当排队等候喂食时，奶牛喜欢和它们的朋友站得靠近些。$\red{FJ}$有$\red{N（}$$\red{2<=N<=1000）}$头奶牛，编号从$\red{1}$到$\red{N，}$沿一条直线站着等候喂食。奶 牛排在队伍中的顺序和它们的编号是相同的。因为奶牛相当苗条，所以可能有两头或者更多奶牛站在同一位置上。

即使说，如果我们想象奶牛是站在一条数轴上的话，允许有两头或更多奶牛拥有相同的横坐标。一些奶牛相互间存有好感，它们希望两者之间的距离不超过一个给定的数$\red{L}$。另一方面，一些奶牛相互间非常反感，它们希望两者间的距离不小于一个给定的数$\red{D}$。

给出$\red{ML}$条关于两头奶牛间有好感的描述，再给出$\red{MD}$条关于两头奶牛间存有反感的描述。$\red{（1<=ML,MD<=10000，}$$\red{1<=L,D<=1000000）}$你的工作是：

如果不存在满足要求的方案，输出$\red{-1}$；如果$\red{1}$号奶牛和$\red{N}$号奶牛间的距离可以任意大，输出$\red{-2}$；否则，计算出在满足所有要求的情况下，$\red{1}$号奶牛和$\red{N}$号奶牛间可能的最大距离。

输入格式

第$\red{1 }$行：三个以空格分隔的整数：$\red{N}$、$\red{ML }$和 $\red{MD}$。

第$\red{2...ML+1 }$行：

每行包含三个以空格分隔的正整数：$\red{A}$、$\red{B }$和 $\red{D，}$其中 $\red{1 <= A < B <= N}$。奶牛 $\red{A }$和 $\red{B }$最多只 能是 $\red{D (1 <= D <= 1,000,000) }$分开。

第$\red{ML+2..ML+MD+1 }$行：

每行包含三个以空格分隔的正整数：$\red{A}$、$\red{B }$和 $\red{D，}$其中 $\red{1 <= A < B <= N}$。

奶牛 $\red{A }$和 $\red{B }$必 须至少为 $\red{D (1 <= D <= 1,000,000) }$分开。

输出格式

第$\red{1}$行：单个整数。如果不可能排列，则输出$\red{-1}$。

如果奶牛$\red{1}$和$\red{N}$可以任意相距，则输出$\red{-2}$。否则，输出奶牛$\red{1}$和$\red{N}$之间的最大可能距离

样例

输入样例

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

输出样例

27

提示

输入详细信息：

有$\red{4}$头牛。奶牛$\red{1}$号和$\red{3}$号不得超过$\red{10}$头除此之外，奶牛$\red{2}$和$\red{4}$之间的距离不得超过$\red{20}$个单位，并且奶牛#$\red{2}$和#$\red{3}$彼此不喜欢，且相距不得少于$\red{3}$个单位。