分数: 600 点
问题陈述
我们有一个二分图 L 左侧顶点和 R 顶点向右。
高桥将在这些顶点安装监控摄像头。
安装摄像头会产生以下费用。
- A_i 日元(日本货币)安装在 i-th (1 \le i \le L) 顶点向左;
- B_j 日元(日本货币)安装在 j-th (1 \le j \le R) 顶点向右。
允许在同一顶点安装多个摄像机。
求满足以下条件安装摄像机所需的最低金额。
- 对于每对整数 (i, j) 这样 1 \le i \le L, 1 \le j \le R,总共有 C_{i,j} 或更多安装在 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 日元如下,这是所需的最低金额。
- 安装 2 相机 1-st 左侧顶点。
- 安装 3 相机 2- 左侧的第一个顶点。
- 安装 2 相机 3-rd 顶点在左侧。
- 安装 1 相机 1-st 右侧顶点。
- 安装 1 相机 3-rd 顶点在右侧。
示例输入 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