← 返回题目列表

AtCoder · arc176_e

E. 最大向量

中文机器翻译题面 查看原题

分数: 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