マッチング公開

左側に $N$ 個、右側に $M$ 個の頂点がある二部グラフがある。左側の頂点 $i$ と右側の頂点 $j$ の間に辺が存在するかどうかを $A_{i,j}$ で表す。$A_{i,j}=1$ なら辺が存在し、$A_{i,j}=0$ なら辺は存在しない。

あなたはグラフのすべての情報を知っているが、別の人は最初、どの辺が存在するかをまったく知らない。

任意の頂点対 $(i,j)$ を選び、その 2 頂点の間に辺が存在するかどうかを公開できる。$(i,j)$ の情報を公開する費用は $C_{i,j}$ である。総費用は、公開したすべての頂点対の費用の合計である。

公開されていない頂点対については、辺の存在は不明のままである。公開された情報と矛盾しない範囲で、各未公開の頂点対について辺が存在するかどうかを互いに独立に自由に決められるものとする。

公開された情報と矛盾しないすべての二部グラフの最大マッチングの大きさが、元のグラフの最大マッチングの大きさと等しいとき、十分な情報を公開したという。

十分な情報を公開するために必要な総費用の最小値を求めよ。

入力は次の形式で与えられる。

$N\ M$ $A_1$ $A_2$

十分な情報を公開するために必要な総費用の最小値を出力せよ。

• $1 \le N,M \le 100$.
• $A_{i,j} \in \{0,1\}$ (, ).