题目描述

给定两个长度为 $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$，可以独立选择要执行哪种操作。

• 对所有满足 $1 \le j \le N$ 的整数 $j$，将 $X_j$ 替换为 $\max(X_j, A_{i,j})$。
• 对所有满足 $1 \le j \le N$ 的整数 $j$，将 $Y_j$ 替换为 $\max(Y_j, A_{i,j})$。

请你求出操作结束后 $\sum_{j=1}^{N} (X_j + Y_j)$ 的最小值。

输入格式

输入以如下格式从标准输入读入。

$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

输出

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

输出

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

输出

3595

说明/提示

限制条件

• $1 \le N \le 10$
• $1 \le M \le 500$
• $1 \le X_j, Y_j, A_{i,j} \le 500$

样例解释 1

一种最优的操作序列如下：

• 将 $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$。

由 ChatGPT 4.1 翻译