310956: CF1913E. Matrix Problem

E. Matrix Problemtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a matrix $a$, consisting of $n$ rows by $m$ columns. Each element of the matrix is equal to $0$ or $1$.

You can perform the following operation any number of times (possibly zero): choose an element of the matrix and replace it with either $0$ or $1$.

You are also given two arrays $A$ and $B$ (of length $n$ and $m$ respectively). After you perform the operations, the matrix should satisfy the following conditions:

1. the number of ones in the $i$-th row of the matrix should be exactly $A_i$ for every $i \in [1, n]$.
2. the number of ones in the $j$-th column of the matrix should be exactly $B_j$ for every $j \in [1, m]$.

Calculate the minimum number of operations you have to perform.

Input

The first line contains two integers $n$ and $m$ ($2 \le n, m \le 50$).

Then $n$ lines follow. The $i$-th of them contains $m$ integers $a_{i,1}, a_{i,2}, \dots, a_{i,m}$ ($0 \le a_{i,j} \le 1$).

The next line contains $n$ integers $A_1, A_2, \dots, A_n$ ($0\le A_i\le m$).

The next line contains $m$ integers $B_1, B_2, \dots, B_m$ ($0\le B_i\le n$).

Output

Print one integer — the minimum number of operations you have to perform, or -1 if it is impossible.

ExamplesInput

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

Output

3

Input

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

Output

3

Input

2 2
0 0
0 0
1 2
0 1

Output

-1

题目大意：
你有一个由 n 行 m 列组成的矩阵 a，矩阵中的每个元素都是 0 或 1。你可以进行任意次数（可能为零）的操作：选择矩阵中的一个元素并将其替换为 0 或 1。你还得到了两个数组 A 和 B（长度分别为 n 和 m）。在执行操作后，矩阵应满足以下条件：

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

计算你必须执行的最小操作次数，如果不可能，则输出 -1。

输入数据格式：
第一行包含两个整数 n 和 m（2 ≤ n, m ≤ 50）。
接下来 n 行，每行包含 m 个整数 a_{i,1}, a_{i,2}, …, a_{i,m}（0 ≤ a_{i,j} ≤ 1）。
下一行包含 n 个整数 A_1, A_2, …, A_n（0 ≤ A_i ≤ m）。
下一行包含 m 个整数 B_1, B_2, …, B_m（0 ≤ B_i ≤ n）。

输出数据格式：
打印一个整数 — 你必须执行的最小操作次数，如果不可能则输出 -1。题目大意： 你有一个由 n 行 m 列组成的矩阵 a，矩阵中的每个元素都是 0 或 1。你可以进行任意次数（可能为零）的操作：选择矩阵中的一个元素并将其替换为 0 或 1。你还得到了两个数组 A 和 B（长度分别为 n 和 m）。在执行操作后，矩阵应满足以下条件： 1. 矩阵的第 i 行中 1 的数量必须恰好为 A_i 对于每个 i ∈ [1, n]。 2. 矩阵的第 j 列中 1 的数量必须恰好为 B_j 对于每个 j ∈ [1, m]。 计算你必须执行的最小操作次数，如果不可能，则输出 -1。 输入数据格式： 第一行包含两个整数 n 和 m（2 ≤ n, m ≤ 50）。 接下来 n 行，每行包含 m 个整数 a_{i,1}, a_{i,2}, …, a_{i,m}（0 ≤ a_{i,j} ≤ 1）。 下一行包含 n 个整数 A_1, A_2, …, A_n（0 ≤ A_i ≤ m）。 下一行包含 m 个整数 B_1, B_2, …, B_m（0 ≤ B_i ≤ n）。 输出数据格式： 打印一个整数 — 你必须执行的最小操作次数，如果不可能则输出 -1。