监控摄像头 2

题目描述

有一个左侧有 $L$ 个顶点、右侧有 $R$ 个顶点的二分图。

高桥要在这些顶点上安装监控摄像头。

安装摄像头会产生以下费用。

在左侧第 $i$ 个（$1 \le i \le L$）顶点上每安装一个摄像头，花费 $A_i$ 日元；

在右侧第 $j$ 个（$1 \le j \le R$）顶点上每安装一个摄像头，花费 $B_j$ 日元。

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

求为了满足以下条件而安装摄像头所需的最小费用。

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

输入格式

输入按以下格式从标准输入给出：

$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}$

输出格式

以整数形式输出答案。

样例

3 4
4 3 6
5 2 3 4
1 2 3 2
2 1 2 3
3 2 1 2

37

可以按如下方式以 37 日元达成目标，这也是所需的最小费用。

在左侧第 1 个顶点上安装 2 个摄像头。

在左侧第 2 个顶点上安装 3 个摄像头。

在左侧第 3 个顶点上安装 2 个摄像头。

在右侧第 1 个顶点上安装 1 个摄像头。

在右侧第 3 个顶点上安装 1 个摄像头。

1 1
10
10
0

0

可能不需要安装任何摄像头。

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

79

数据范围

• 输入均为整数。
• $1 \le L, R \le 100$
• $1 \le A_i, B_i \le 10$
• $0 \le C_{i,j} \le 100$