問題文

$N$頂点$M$辺の有向グラフが与えられます。$i$番目の辺は頂点$x_i$から頂点$y_i$へ向かう有向辺です。各頂点には整数$B_i$が書かれており、各頂点ははじめ白で塗られています。

次の操作を順に行うとき、黒で塗られている頂点に書かれた整数の和の最大値を求めてください。

• 操作$1$：$0$個以上の頂点を選択し、選択した頂点からたどり着ける頂点を黒で塗る。
• 操作$2$：$0$個以上の頂点を選択し、選択した頂点からたどり着ける頂点を白で塗る。

制約

• $1\leq N\leq 1000$
• $0\leq M\leq \min(N(N-1),1000)$
• $-10^9\leq B_i\leq 10^9$
• $1\leq x_i,y_i\leq N$
• $x_i\neq y_i$
• $(x_i,y_i)\neq (x_j,y_j) (i\neq j)$

入力

入力はすべて整数である。

出力

答えを一行に出力せよ。

サンプル

3 2
2 -2 1
1 2
2 3

2

操作$1$で頂点$1$を選び、頂点$1,2,3$を黒で塗ります。 操作$2$で頂点$2$を選び、頂点$2,3$を白で塗ります。このとき、黒で塗られている頂点に書かれた整数の和は$B_1=2$となります。

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

2

グラフが閉路を含むこともあります。操作$1$で頂点$1,3$を選び、$2$番目の操作で頂点$5$を選ぶのが最適です。

3 0
-3 -1 -4

0

$1$つも選ばなくても良いです。