매칭 공개

왼쪽에 $N$개의 정점, 오른쪽에 $M$개의 정점이 있는 이분 그래프가 있다. 왼쪽 정점 $i$와 오른쪽 정점 $j$ 사이의 간선 존재 여부를 $A_{i,j}$로 나타낸다. $A_{i,j}=1$이면 간선이 있고, $A_{i,j}=0$이면 간선이 없다.

당신은 그래프의 모든 정보를 알고 있지만, 다른 사람은 어떤 간선이 있는지 전혀 알지 못한다.

당신은 원하는 정점 쌍 $(i,j)$를 골라 두 정점 사이에 간선이 있는지 없는지를 공개할 수 있다. $(i,j)$의 정보를 공개하는 데에는 $C_{i,j}$의 비용이 든다. 여러 정보를 공개했을 때의 총비용은 공개한 모든 쌍의 비용 합이다.

공개하지 않은 정점 쌍의 간선 존재 여부는 알 수 없다. 공개된 정보와 모순되지 않는 한, 각 미공개 정점 쌍에 대해 간선의 존재 여부를 서로 독립적으로 임의로 정할 수 있다고 하자.

이렇게 만들 수 있는 모든 이분 그래프의 최대 매칭 크기가 원래 그래프의 최대 매칭 크기와 같다면, 충분한 정보를 공개했다고 한다.

충분한 정보를 공개하는 데 필요한 총비용의 최솟값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$N\ M$ $A_1$ $A_2$

충분한 정보를 공개하는 데 필요한 총비용의 최솟값을 출력한다.

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