1392 - 決まりごとの多いジム

問題

イヅア村のスポーツジムには$1$から$N$までの番号が付いた$N$台のトレーニング機器があります。トレーニング機器を１回利用するには、その機器の番号が書かれたチケットが１枚必要です。トレーニング機器を１回利用したときの消費カロリーは、機器ごとに決まっています。

このスポーツジムのチケットを何枚かもらったアツシ君は、運動不足解消のためにジムに行きました。このジムでは、利用者が運動をやりすぎて体を痛めないように、機器の利用回数にルールがあります。たとえば、「２番の機器は３番の機器よりも５回以上多く使ってはいけません」というようなルールです。機器を使う人は、ルールを守って機器を利用しなければなりません。

アツシ君は、もらったチケットを使って、ルールで許される範囲でなるべく多くのカロリーを消費したいと思っています。 もらったチケットとそれぞれの機器の情報が与えられたとき、ルールを守ったときの消費カロリーの最大値を求めるプログラムを作成しなさい。

入力

入力は以下の形式で与えられる。

$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$

１行目にトレーニング機器の台数$N$ ($1 \leq N \leq 100,000$)とルールの数$R$ ($0 \leq R \leq 100,000$)が与えられる。続く$N$行に、$i$番の機器について、アツシ君がもらったチケットの枚数$t_i$ ($1 \leq t_i \leq 200,000$)とその機器を使ったときの消費カロリー$e_i$ ($0 \leq e_i \leq 100,000$)が与えられる。続く$R$行に、「$a_i$番の機器は$b_i$番の機器よりも$c_i$回以上多く使ってはいけません」というルールを表す数$a_i$ ($1 \leq a_i \leq N$)、$b_i$ ($1 \leq b_i \leq N$)、$c_i$ ($1 \leq c_i \leq 100,000$)が与えられる。

入力は以下の制約を満たす。

• 同じ機器のペアに対するルールは１度しか与えられない($i \ne j$なら$a_i \ne a_j$または$b_i \ne b_j$)。
• 同じ機器自身に対するルールは与えられない($a_i \ne b_i$)。

出力

消費カロリーの最大値を１行に出力する。

入出力例

入力例１

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

出力例１

45

もらったチケットを使って、ルールを守って使える各機器の最大の回数は、$1$番が$5$回、$2$番が$7$回、$3$番が$6$回なので、消費カロリーの最大値は$5 \times 1 + 7 \times 4 + 6 \times 2 = 45$となる。

入力例２

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

出力例２

26

入力例３

1 0
200000 100000

出力例３

20000000000