← 返回题目列表

AtCoder · abc224_h

H. 监控摄像头 2

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

分数: 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