[ARC176E] Max Vector

### 题目描述 给你两个长度为 $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$, $X_j$ 替换为 $\max(X_j,A_{i,j})$。 - 对于所有 $1 \le j \le N$，$Y_j$ 替换为 $\max(Y_j,A_{i,j})$。 求所有操作后 $\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$

[problemUrl]: https://atcoder.jp/contests/arc176/tasks/arc176_e 長さ $ N $ の正整数列 $ X=(X_1,X_2,\dots,X_N),Y=(Y_1,Y_2,\dots,Y_N) $ が与えられます。 また、長さ $ N $ の正整数列が $ M $ 個与えられます。$ 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} $

答えを出力せよ。

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

21

3 5
4 13 10
14 9 4
4 6 4
13 18 16
8 13 5
7 18 17
20 20 14

84

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 $ ### Sample Explanation 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 $ が達成できます。