Cow Lineup

FJ has N cows numbered from 1 to N standing in a line (in the order of their numbers). Note that two or more cows can share the same position on a number line. Some cows like each other and require that their separation is at most a given distance. Others dislike each other and require that they be separated by at least a given distance.

You are given two sets of constraints:

• ML constraints: Each constraint is given by three integers \(a, b, d\) (with \(1 \le a < b \le N\)) and requires that the distance between cow \(a\) and cow \(b\) satisfies \(x_b - x_a \le d\). In other words, cows that like each other cannot be separated by more than \(d\) units.
• MD constraints: Each constraint is given by three integers \(a, b, d\) (with \(1 \le a < b \le N\)) and requires that \(x_b - x_a \ge d\). That is, cows that dislike each other must be separated by at least \(d\) units.

In addition, since the cows are in the order of their numbering, they satisfy the natural ordering property \(x_1 \le x_2 \le \cdots \le x_N\) (i.e. the distance between consecutive cows is nonnegative, so \(x_{i+1} - x_i \ge 0\) for all \(1 \le i < N\)).

Your task is to compute, if possible, the maximum possible distance between cow 1 and cow N, i.e. the maximum possible value of \(x_N - x_1\), that satisfies all the constraints. If the constraints are inconsistent such that no valid assignment exists, output -1. If the distance is unbounded (i.e. can be made arbitrarily large), output -2.

Note: All formulas are rendered in LaTeX format. For example, the ML constraint is formulated as \(x_b - x_a \le d\) and the MD constraint as \(x_b - x_a \ge d\).

inputFormat

The first line contains three integers: N (the number of cows, with \(2 \le N \le 1000\)), ML (the number of "like" constraints, with \(1 \le ML \le 10000\)), and MD (the number of "dislike" constraints, with \(1 \le MD \le 10000\)).

The next ML lines each contain three integers a b d representing a like constraint: for cows \(a\) and \(b\) (with \(a < b\)), the separation must satisfy \(x_b - x_a \le d\).

The following MD lines each contain three integers a b d representing a dislike constraint: for cows \(a\) and \(b\) (with \(a < b\)), the separation must satisfy \(x_b - x_a \ge d\).

It is implicitly assumed that for every \(1 \le i < N\), the cows satisfy \(x_{i+1} - x_i \ge 0\>.

outputFormat

Output a single integer representing the maximum possible distance between cow 1 and cow N (i.e. \(x_N - x_1\)). If there is no valid assignment that satisfies the constraints, output -1. If the maximum distance is unbounded, output -2.

sample

3 1 1
1 3 10
1 2 5

10