← 返回题目列表

Codeforces · 1913/E

E. 矩阵问题

中文机器翻译题面 查看原题

给定一个矩阵 $$$a$$$,由 $$$n$$$ 行和 $$$m$$$ 列组成。矩阵的每个元素都等于 $$$0$$$ 或 $$$1$$$。

您可以执行以下操作任意次数(可能为零):选择矩阵的一个元素并将其替换为 $$$0$$$ 或 $$$1$$$。

您还得到两个数组 $$$A$$$ 和 $$$B$$$ (长度分别为 $$$n$$$ 和 $$$m$$$)。执行运算后,矩阵应满足以下条件:

1. 对于 [1, n]$$$ 中的每个 $$$i,矩阵第 $$$i$$$ 行中 1 的数量应恰好为 $$$A_i$$$。
2. 对于 [1, m]$$$ 中的每个 $$$j,矩阵第 $$$j$$$ 列中 1 的数量应恰好为 $$$B_j$$$。

计算您必须执行的最少操作数。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n, m \le 50$$$)。

然后是 $$$n$$$ 行。其中第 $$$i$$$ 包含 $$$m$$$ 整数 $$$a_{i,1}, a_{i,2}, \dots, a_{i,m}$$$ ($$$0 \le a_{i,j} \le 1$$$)。

下一行包含 $$$n$$$ 整数 $$$A_1, A_2, \dots, A_n$$$ ($$$0\le A_i\le m$$$)。

下一行包含 $$$m$$$ 整数 $$$B_1, B_2, \dots, B_m$$$ ($$$0\le B_i\le n$$$)。

输出

打印一个整数 — 您必须执行的最少操作数,如果不可能,则打印 -1。

示例

输入 #1

3 3
0 0 0
0 0 0
0 0 0
1 1 1
1 1 1

输出 #1

3

输入 #2

3 3
1 1 1
1 1 1
1 1 1
3 2 1
1 2 3

输出 #2

3

输入 #3

2 2
0 0
0 0
1 2
0 1

输出 #3

-1