燃やす埋める練習問題２

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

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

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

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

3 3 4
1 1 1
1 1 1
1 1
2 2
2 3
3 1

4

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

3 3 4
1 3 1
3 1 1
1 1
2 2
2 3
3 1

6

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