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

输入 #1

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

输出 #1

37

输入输出样例 #2

输入 #2

1 1
10
10
0

输出 #2

0

输入输出样例 #3

输入 #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

说明/提示

限制条件

• 所有输入均为整数。
• $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 翻译