AT_abc224_h.[ABC224H] Security Camera 2

有一个二分图，左侧有 $L$ 个顶点，右侧有 $R$ 个顶点。
高桥君打算在这个二分图的每个顶点上安装摄像头。
每安装一个摄像头需要支付如下费用：

• 在第 $i$ 个左侧顶点上安装 $1$ 个摄像头需要 $A_i$ 日元（$1 \leq i \leq L$）。
• 在第 $j$ 个右侧顶点上安装 $1$ 个摄像头需要 $B_j$ 日元（$1 \leq j \leq R$）。

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

请你求出，在满足以下条件的情况下，所需的最小总费用：

• 对于所有满足 $1 \leq i \leq L,\ 1 \leq j \leq 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}$

请输出所需的最小总费用，结果为整数。

限制条件

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

样例解释 1

如下安装摄像头可以达到总费用 $37$ 日元，并且这是最小值：

• 在第 $1$ 个左侧顶点安装 $2$ 个摄像头。
• 在第 $2$ 个左侧顶点安装 $3$ 个摄像头。
• 在第 $3$ 个左侧顶点安装 $2$ 个摄像头。
• 在第 $1$ 个右侧顶点安装 $1$ 个摄像头。
• 在第 $3$ 个右侧顶点安装 $1$ 个摄像头。

样例解释 2

也存在一种情况，不需要安装任何摄像头。

由 ChatGPT 4.1 翻译