Gym with Many Rules

　

The gym in Izua Village has $N$ units of training equipment, numbered from 1 to $N$. To use a piece of training equipment once, you need one ticket with the number of the equipment written on it. The number of calories burned when using each piece of training equipment is determined for each piece of equipment.

After receiving some tickets for this gym, Atsushi went to the gym to get some exercise. At this gym, there are rules on the number of times the equipment can be used so that users don't overdo their exercise and hurt their bodies. For example, the rules say, "You can't use equipment number 2 more than or equalt to 5 times than equipment number 3". People who use the equipments have to follow the rules.

Atsushi wants to use the ticket he received to burn as many calories as possible within the limits allowed by the rules. Given the ticket he received and the information about each equipment, write a program to find the maximum number of calories he can consume by following the rules.

Input

The input is given in the following form.

$N$ $R$
$t_1$ $e_1$
$t_2$ $e_2$
:
$t_N$ $e_N$
$a_1$ $b_1$ $c_1$
$a_2$ $b_2$ $c_2$
:
$a_R$ $b_R$ $c_R$

In the first line, the number of training equipments $N$ ($1 \leq N \leq 100,000$) and the number of rules $R$ ($0 \leq R \leq 100,000$) are given. In the following $N$ lines, the number of tickets Atsushi received for equipment $i$, $t_i$ ($1 \leq t_i \leq 200,000$), and the calories consumed when using the equipment $e_i$ ($0 \leq e_i \leq 100,000$) are given. In the following $R$ lines, we are given the numbers $a_i$ ($1 \leq a_i \leq N$), $b_i$ ($1 \leq b_i \leq N$), and $c_i$ ($1 \leq c_i \leq 100,000$) which represent the rule that the equipment numbered $a_i$ must not be used more than or equal to $c_i$ times than the equipment numbered $b_i$.

The input satisfies the following constraints.

• Rules for the same pair of equipments can be given only once ($a_i \ne a_j$ or $b_i \ne b_j$ for $i \ne j$)。
• No rule can be given for the same equipment itself($a_i \ne b_i$)。

Output

Output the maximum number of calories consumed in a line.

Sample Input and Output

Sample Input 1

3 2
5 1
10 4
6 2
2 1 3
3 2 1

Sample Output 1

45

The maximum number of times each equipment can be used with the ticket you received and following the rules is $5$ times for the number $1$, $7$ times for the number $2$, and $6$ times for the number $3$, so the maximum number of calories consumed is $5 \times 1 + 7 \times 4 + 6 \times 2 = 45$.

Sample Input 2

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

Sample Output 2

26

Sample Input 3

1 0
200000 100000

Sample Output 3

20000000000

---