H - 安全摄像头2

得分：600分

问题描述

我们有一张$L$个顶点在左边和$R$个顶点在右边的二分图。 Takahashi将在这些顶点上安装监视摄像头。 安装摄像头会产生以下费用：

• 对于左边第$i$个顶点（$1 \leq i \leq L$），每安装一个摄像头需要$A_i$日元；
• 对于右边第$j$个顶点（$1 \leq j \leq R$），每安装一个摄像头需要$B_j$日元。

可以在同一个顶点上安装多个摄像头。

找到满足以下条件所需的最少金额：

• 对于每对整数$(i, j)$满足$1 \leq i \leq L, 1 \leq j \leq R$，在左边第$i$个顶点和右边第$j$个顶点中共安装了$C_{i,j}$或更多的摄像头。

约束条件

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

输入

输入遵循以下格式，从标准输入中读入：

L R
A_1 A_2 ... A_L
B_1 B_2 ... B_R
C_{1,1} C_{1,2} ... C_{1,R}
C_{2,1} C_{2,2} ... C_{2,R}
...
C_{L,1} C_{L,2} ... 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