問題文

頂点数$|L|,|R|$、辺数$M$の二部グラフおよび各頂点の重み$w_{L_i},w_{R_i}$が与えられます。$j$番目の辺は頂点$L_{x_j}$と頂点$R_{y_j}$を結んでいます。このグラフにおける最大重み独立集合を求め、重みの和を出力してください。

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

制約

• $1 \leq |L|,|R| \leq 100$
• $0 \leq M \leq L\times R$
• $1\leq w_{L_i},w_{R_i} \leq 10^9$
• $1\leq x_j\leq L$
• $1\leq y_j\leq R$
• $i\neq j \Leftrightarrow (x_i,y_i)\neq (x_j,y_j)$

入力

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

出力

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

サンプル

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

4

重みがすべて$1$なので最大独立集合の大きさと一致します。$\{L_1,L_3,R_2,R_3\}$が重み最大となります。

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

6

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