燃やす埋める練習問題2

2 secs 1024 MB
_kanpurin_

問題文


頂点数、辺数の二部グラフおよび各頂点の重みが与えられます。番目の辺は頂点と頂点を結んでいます。このグラフにおける最大重み独立集合を求め、重みの和を出力してください。

最大重み独立集合とは独立集合のうち、頂点の重みの和が最大となるもののことです。

制約


入力


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







出力


計算結果を一行に出力せよ。

サンプル


入力1
3 3 4
1 1 1
1 1 1
1 1
2 2
2 3
3 1
出力1
4

重みがすべてなので最大独立集合の大きさと一致します。が重み最大となります。

入力2
3 3 4
1 3 1
3 1 1
1 1
2 2
2 3
3 1
出力2
6

グラフはサンプルと同じですが重みが異なります。独立集合の大きさが最大である必要はありません。が重み最大となります。

Submit


Go (1.14)