The teacher has assigned a group project. Before this, the teacher divided the $2n$ students in the class into $n$ groups, with two students in each group. Specifically, student $1$ and student $2$ are in a group, student $3$ and student $4$ are in a group, ..., and student $2n-1$ and student $2n$ are in a group.

The teacher lets each team decide their own division of labor. Whether they cooperate or not has become a major issue. Everyone decides to determine this by voting. First, each person decides whether they are willing to cooperate with their teammate. Due to personal reasons and the identity of their assigned teammate, different people have different levels of willingness to cooperate. For the $i$-th student, choosing "willing" results in $c_i$ dissatisfaction, while choosing "unwilling" results in $d_i$ dissatisfaction.

If both teammates choose "willing," they can choose to cooperate or not cooperate based on the actual situation. However, if one teammate chooses "unwilling," they must not cooperate.

There are $m$ one-way "like" relationships among the students, where a relationship is defined as "$A$ likes $B$." In such a relationship, if $A$ does not cooperate with their teammate and $B$ chooses "willing," $A$ will feel slightly frustrated, resulting in $a_i$ dissatisfaction. If $A$ votes "unwilling" but $B$ successfully cooperates with their teammate, $A$ will feel envious and jealous, resulting in $b_i$ dissatisfaction. (Since this setup becomes strange when $A$ and $B$ are in the same group, the problem guarantees that such cases will not occur.) Here, $i$ denotes the $i$-th relationship.

If a student $i$ chooses "willing" but their teammate chooses "unwilling," they will incur $e_i$ dissatisfaction because of their teammate.

Find the minimum total dissatisfaction across all possible scenarios.

The first line contains two integers $n$ and $m$.

The next $2n$ lines each contain three integers $c_i, d_i, e_i$.

The next $m$ lines each contain four positive integers $A, B, a_i, b_i$.

Output a single integer representing the answer.

Subtasks

It is guaranteed that $1 \le n \le 5000$, $0 \le m \le 10000$, and $1 \le a_i, b_i, c_i, d_i, e_i \le 10^9$.

Examples

Input 1

2 1
8 6 7
5 2 8
7 1 5
6 5 8
1 4 4 3

Output 1

14