题目描述

我们有一个二分图，左边有$L$个顶点，右边有$R$个顶点。
Takahashi将在这些顶点上安装监控摄像头。
安装摄像头会产生以下成本。

• 安装在第$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}$个摄像头。

约束条件

• 输入中的所有值都是整数。
• $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