分数: 800 点
问题陈述
你有两个长度-N 正整数序列: X=(X_1,X_2,\dots,X_N) 和 Y=(Y_1,Y_2,\dots,Y_N).
此外,您还获得 M 长度-N 正整数序列。的 i第一个序列是 A_i = (A_{i,1},A_{i,2},\dots,A_{i,N}).
对于每个 i = 1,2,\dots,M,您必须执行以下操作之一。您可以独立选择每个操作要执行的操作 i.
- 替换 X_j 与 \max(X_j,A_{i,j}) 对于所有整数 j 这样 1 \le j \le N.
- 替换 Y_j 与 \max(Y_j,A_{i,j}) 对于所有整数 j 这样 1 \le j \le N.
找到以下的最小可能值 \sum_{j=1}^{N} (X_j + Y_j) 完成所有操作后。
约束
- 1 \le N \le 10
- 1 \le M \le 500
- 1 \le X_j, Y_j, A_{i,j} \le 500
输入
输入由标准输入按以下格式给出:
N M
X_1 X_2 \dots X_N
Y_1 Y_2 \dots Y_N
A_{1,1} A_{1,2} \dots A_{1,N}
A_{2,1} A_{2,2} \dots A_{2,N}
\vdots
A_{M,1} A_{M,2} \dots A_{M,N}
输出
打印答案。
示例输入 1
3 2 4 4 2 3 1 5 2 5 2 1 2 4
示例输出 1
21
一种最佳操作顺序如下:
- 替换 X_j 与 \max(X_j,A_{1,j}), 制作 X = (4,5,2).
- 替换 Y_j 与 \max(Y_j,A_{2,j}), 制作 Y = (3,2,5).
这个操作序列实现了 \sum_{j=1}^{N} (X_j + Y_j) = 21.
示例输入 2
3 5 4 13 10 14 9 4 4 6 4 13 18 16 8 13 5 7 18 17 20 20 14
示例输出 2
84
示例输入 3
5 12 330 68 248 387 491 295 366 376 262 192 280 121 17 168 455 288 179 210 378 490 150 275 165 264 287 66 331 207 282 367 303 215 456 214 18 227 326 103 443 427 395 57 107 350 227 318 231 146 2 116 57 325 124 383 260 147 319 23 177 445 254 198 32 85 56 68 177 356 41 471
示例输出 3
3595