布局 Layout

题号：NC50390
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

FJ有N头奶牛 $(2 \leq N \leq1000)$ ，编号为 $1 \ldots N$ 。奶牛们将按照编号顺序排成一列队伍（可能有多头奶牛在同一位置上）。换句话说，假设i号奶牛位于 $P_{ \! \;i}$ ，则 $P_{ \,1} \leq P_{ \,2} \leq \ldots \leq P_{ \! \;N}$ 。
有些奶牛是好基友，它们希望彼此之间的距离小于等于某个数。有些奶牛是情敌，它们希望彼此之间的距离大于等于某个数。
给出 $M_L$ 对好基友的编号，以及它们希望彼此之间的距离小于等于多少；又给出 $M_D$ 对情敌的编号，以及它们希望彼此之间的距离大于等于多少 $(1 \leq M_L,$ $M_D \leq 10^4)$ 。
请计算：如果满足上述所有条件，1号奶牛和N号奶牛之间的距离（ $P_{ \! \;N}-P_{ \,1}$ ）最大为多少。

输入描述:

第一行：三个整数，用空格分隔。
第行：每行三个整数A,B,D，用空格分隔，表示。
第行：每行三个整数A,B,D，用空格分隔，表示。
保证.

输出描述:

一行，一个整数。如果没有合法方案，输出.如果有合法方案，但1号奶牛可以与N号奶牛相距无穷远，输出.否则，输出1号奶牛与N号奶牛间的最大距离。

示例1

输入

复制

输出

复制

说明

这四头牛分别位于0,7,10,27。

备注:

对于全部数据，。