イヅア村のスポーツジムには$1$から$N$までの番号が付いた$N$台のトレーニング機器があります。トレーニング機器を1回利用するには、その機器の番号が書かれたチケットが1枚必要です。トレーニング機器を1回利用したときの消費カロリーは、機器ごとに決まっています。
このスポーツジムのチケットを何枚かもらったアツシ君は、運動不足解消のためにジムに行きました。このジムでは、利用者が運動をやりすぎて体を痛めないように、機器の利用回数にルールがあります。たとえば、「2番の機器は3番の機器よりも5回以上多く使ってはいけません」というようなルールです。機器を使う人は、ルールを守って機器を利用しなければなりません。
アツシ君は、もらったチケットを使って、ルールで許される範囲でなるべく多くのカロリーを消費したいと思っています。 もらったチケットとそれぞれの機器の情報が与えられたとき、ルールを守ったときの消費カロリーの最大値を求めるプログラムを作成しなさい。
入力は以下の形式で与えられる。
$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$
1行目にトレーニング機器の台数$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$)が与えられる。
入力は以下の制約を満たす。
消費カロリーの最大値を1行に出力する。
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