Hamako Online Judge

TLE
1sec

MLE
64MB

得点
100

ストーリー

ここは都市NOW_MAN_ZAWのはずれにある緑豊かな田園風景が広がっている良さみが深い土地、OHTSUNO_ZIKA町である。

しかしここはただの町ではない、ここはコーヒーが世界一おいしいと呼ばれている店が点在しているとかいうインフレ待ったなしの神だ。

そんなわけで、ここには都市の人や、他の町の人たちが押し寄せてくる超最強の土地だ。神だ。すごい。プロ。

つまり、私たちはこのOHTSUNO_ZIKA町を全面に推していきたい！！！！！！ウェイ！ｗ

町の体験者、ナウ人間くん「旅なので、満足しよう、旅なので( $575$ )」

ただしこのOHTSUNO_ZIKA町がいくら田園風景が広がっていようと急勾配ばっかの山地であることは皆さんはご存じだろう。

問題

おいしいコーヒーを売る店が $N$ 個ある。店と店を結ぶ道が $M$ 本ある。
この道は必ず $2$ つの店を結んでいるものとし、 $3$ つ以上を結ばない。

OHTSUNO_ZIKA町はでこぼこしているのでそれぞれの店の標高 $H_i$ が異なり、また店のコーヒーのおいしさ $D_i$ も異なる。

ナウ人間くんは、まず任意の店 $i$ にヘリコプターから落下する。
ナウ人間くんは山を登りたくない(平坦な土地も歩きたくない)ので、山を下りる形で、店に寄っていっておいしいコーヒーを買って飲んでいく。
つまり、店 $i$ から移動する店 $j$ の標高は、 $H_i > H_j$ である。

課題　

適切に降りる店を選んだとき、飲んだコーヒーのおいしさの総和の最大を求めよ。

入力

$1$ 行目に店の数 $N$ 、道の数 $M$ が与えられる。

$2$ 〜 $1 + N$ 行目まで、それぞれの店の標高 $H_i$ , それぞれの店のおいしさ $D_i$ が与えられる。

$2 + N$ 〜 $1 + N + M$ 行目まで、店と店を結ぶ道 $A_j$ , $B_j$ が与えられる。

道は店 $A_j$ と店 $B_j$ を結んでいることになる。

$N$ $M$
$H_1$ $D_1$
$H_2$ $D_2$
     .
     .
     .
$H_N$ $D_N$
$A_1$ $B_1$
$A_2$ $B_2$
     .
     .
     .
$A_M$ $B_M$

出力

適切に降りる店を選んだとき、飲んだコーヒーのおいしさの総和の最大を出力せよ。

制約

制約の数値はすべて整数であることが保証される。
$1 \leq N \leq 10^5$
$0 \leq M \leq 2 × 10^5$

$1 \leq H_i \leq 10^9$
$1 \leq D_i \leq 10^4$
$1 \leq i \leq N$

$1 \leq A_j , B_j \leq N$
$1 \leq j \leq M$

入出力例

入力例1

出力例1

解説

店 $1$ にヘリコプターが降りる。そうすると、店 $2$ 、店 $5$ と降りることができるため、
店 $1$ のおいしさ $4$ , 店 $2$ のおいしさ $1$ , 店 $5$ のおいしさ $4$ を足して、
$ 4 + 1 + 4 $ より、$9$ となり、これが最大となる。

入力例2

出力例2

PCKの予選7問目くらいの問題を想定しました。解いてください！！！！

難しい問題ってどう作ればいいのか全然わからん(5,6問目くらいになった)！

007 - おいしいコーヒー(The coffee is delicious!)