Minimize Total Dissatisfaction

In a class, the teacher has pre-divided the 2(n) students into (n) groups (pairs): (1,2), (3,4), …, (2(n)-1,2(n)). For a group, the two team members each cast a vote on whether they are willing to cooperate with their partner. For the (i)th student, voting “willing” costs (c_i) units of dissatisfaction, while voting “not willing” costs (d_i). Moreover, if a student votes willing but her teammate votes not willing, she suffers an extra cost of (e_i).

If both members in a group vote willing, the group may then decide on whether to actually cooperate or not. In such a group you may choose the cooperation outcome ((Y=1)) or non‐cooperation outcome ((Y=0)) arbitrarily. However, if at least one student in a group votes not willing, the outcome is forced to non–cooperation ((Y=0)).

In addition, there are (m) one–directional like relations among the students. In a relation where student (A) likes student (B) (with associated costs (a) and (b)), the following extra dissatisfaction is incurred:

( \begin{array}{ll} \text{If student } A \text{’s team does not cooperate (i.e. }Y_A=0\text{) and } B \text{ votes willing, then add } a,\[6pt] \text{If student } A \text{ votes not willing and } B \text{’s team cooperates (i.e. }Y_B=1\text{), then add } b.\ \end{array} )

Determine the voting strategy for each student and the cooperation decision for each group (when allowed) such that the total dissatisfaction (the sum of individual vote costs, potential extra costs due to teammate’s vote, and like–relation penalties) is minimized.

inputFormat

The first line contains two integers (n) and (m) — the number of groups and the number of like relations, respectively. There are (2n) students numbered from 1 to (2n), grouped into pairs as follows: (1,2), (3,4), …, (2n-1,2n).

Then follow (2n) lines. The (i)th of these lines contains three integers (c_i), (d_i), and (e_i), representing the dissatisfaction cost for student (i) when voting “willing”, when voting “not willing”, and the extra dissatisfaction incurred if they vote willing but their teammate does not, respectively.

Then there are (m) lines, each containing four integers: (A), (B), (a), and (b), representing a one–directional like relation where student (A) likes student (B) and incurs an extra cost of (a) if (A)’s team fails to cooperate while (B) votes willing, or an extra cost of (b) if (A) votes not willing while (B)’s team cooperates.

outputFormat

Output a single integer representing the minimum total dissatisfaction achievable.

sample

1 1
1 3 2
2 1 2
1 2 4 5

3