102247: [AtCoder]ABC224 H - Security Camera 2

Problem Statement

We have a bipartite graph with $L$ vertices to the left and $R$ vertices to the right.
Takahashi will install surveillance cameras in these vertices.
Installing cameras incurs the following cost.

• $A_i$ yen (the Japanese currency) for each camera installed in the $i$-th $(1 \le i \le L)$ vertex to the left;
• $B_j$ yen (the Japanese currency) for each camera installed in the $j$-th $(1 \le j \le R)$ vertex to the right.

It is allowed to install multiple cameras on the same vertex.

Find the minimum amount of money needed to install cameras to satisfy the following condition.

• For every pair of integers $(i, j)$ such that $1 \le i \le L, 1 \le j \le R$, there is a total of $C_{i,j}$ or more cameras installed in the $i$-th vertex to the left and $j$-th vertex to the right.

Constraints

• All values in input are integers.
• $1 \le L,R \le 100$
• $1 \le A_i,B_i \le 10$
• $0 \le C_{i,j} \le 100$

Input

Input is given from Standard Input in the following format:

$L$ $R$
$A_1$ $A_2$ $\dots$ $A_L$
$B_1$ $B_2$ $\dots$ $B_R$
$C_{1,1}$ $C_{1,2}$ $\dots$ $C_{1,R}$
$C_{2,1}$ $C_{2,2}$ $\dots$ $C_{2,R}$
$\vdots$
$C_{L,1}$ $C_{L,2}$ $\dots$ $C_{L,R}$

Output

Print the answer as an integer.

Sample Input 1

3 4
4 3 6
5 2 3 4
1 2 3 2
2 1 2 3
3 2 1 2

Sample Output 1

37

You can achieve the objective for $37$ yen as follows, which is the minimum amount required.

• Install $2$ cameras on the $1$-st vertex in the left.
• Install $3$ cameras on the $2$-nd vertex in the left.
• Install $2$ cameras on the $3$-rd vertex in the left.
• Install $1$ camera on the $1$-st vertex in the right.
• Install $1$ camera on the $3$-rd vertex in the right.

Sample Input 2

1 1
10
10
0

Sample Output 2

0

No camera may be needed.

Sample Input 3

5 6
3 2 6 7 5
4 9 8 6 2 3
2 0 2 1 1 0
2 3 2 1 0 0
2 2 4 0 2 2
4 1 0 3 0 2
1 0 0 2 2 5

Sample Output 3

79

问题描述

我们有一个二分图，左侧有$L$个顶点，右侧有$R$个顶点。

高桥将在这些顶点上安装监控摄像头。

安装摄像头的费用如下：

• 在第$(1 \le i \le L)$个左侧顶点上安装每个摄像头需要$A_i$日元（日本货币）；
• 在第$(1 \le j \le R)$个右侧顶点上安装每个摄像头需要$B_j$日元（日本货币）。

允许在同一个顶点上安装多个摄像头。

找到满足以下条件所需的最低金额。

• 对于每对整数$(i, j)$，使得$1 \le i \le L, 1 \le j \le R$，在第$i$个左侧顶点和第$j$个右侧顶点上总共安装$C_{i,j}$或更多的摄像头。

约束

• 输入中的所有值都是整数。
• $1 \le L,R \le 100$
• $1 \le A_i,B_i \le 10$
• $0 \le C_{i,j} \le 100$

输入

输入从标准输入中给出，格式如下：

$L$ $R$
$A_1$ $A_2$ $\dots$ $A_L$
$B_1$ $B_2$ $\dots$ $B_R$
$C_{1,1}$ $C_{1,2}$ $\dots$ $C_{1,R}$
$C_{2,1}$ $C_{2,2}$ $\dots$ $C_{2,R}$
$\vdots$
$C_{L,1}$ $C_{L,2}$ $\dots$ $C_{L,R}$

输出

打印一个整数作为答案。

样例输入 1

3 4
4 3 6
5 2 3 4
1 2 3 2
2 1 2 3
3 2 1 2

样例输出 1

37

您可以通过以下方式以37日元实现目标，这是所需最低金额。

• 在左侧的第1个顶点上安装2个摄像头。
• 在左侧的第2个顶点上安装3个摄像头。
• 在左侧的第3个顶点上安装2个摄像头。
• 在右侧的第1个顶点上安装1个摄像头。
• 在右侧的第3个顶点上安装1个摄像头。

样例输入 2

1 1
10
10
0

样例输出 2

0

可能不需要摄像头。

样例输入 3

5 6
3 2 6 7 5
4 9 8 6 2 3
2 0 2 1 1 0
2 3 2 1 0 0
2 2 4 0 2 2
4 1 0 3 0 2
1 0 0 2 2 5

样例输出 3

79