Score : $600$ points

问题描述

我们有一个具有$L$个左侧顶点和$R$个右侧顶点的二分图。
高桥将在这些顶点安装监控摄像头。
安装摄像头会产生以下成本：

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

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

求满足以下条件时，安装摄像头所需的最小金额。

• 对于所有整数对 $(i, j)$，满足 $1 \le i \le L, 1 \le j \le R$，在左侧第 $i$ 个顶点和右侧第 $j$ 个顶点总共安装了至少 $C_{i,j}$ 个摄像头。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 09:52:35