燃やす埋める練習問題４

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

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

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

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

答えを一行に出力せよ。

3 2
2 -2 1
1 2
2 3

2

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

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

2

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

3 0
-3 -1 -4

0

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