E - Max Vector Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

長さ 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) の最小値を求めてください。

制約

  • 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

Score: 800 points

Problem Statement

You are given two length-N sequences of positive integers: X=(X_1,X_2,\dots,X_N) and Y=(Y_1,Y_2,\dots,Y_N).

Additionally, you are given M length-N sequences of positive integers. The i-th sequence is A_i = (A_{i,1},A_{i,2},\dots,A_{i,N}).

For each i = 1,2,\dots,M, you must perform one of the following operations. You can independently choose which operation to perform for each i.

  • Replace X_j with \max(X_j,A_{i,j}) for all integers j such that 1 \le j \le N.
  • Replace Y_j with \max(Y_j,A_{i,j}) for all integers j such that 1 \le j \le N.

Find the minimum possible value of \sum_{j=1}^{N} (X_j + Y_j) after all operations.

Constraints

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

Input

The input is given from Standard Input in the following format:

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}

Output

Print the answer.

Sample Input 1

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

Sample Output 1

21

One optimal sequence of operations is as follows:

  • Replace X_j with \max(X_j,A_{1,j}), making X = (4,5,2).
  • Replace Y_j with \max(Y_j,A_{2,j}), making Y = (3,2,5).

This sequence of operations achieves \sum_{j=1}^{N} (X_j + Y_j) = 21.

Sample Input 2

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

Sample Output 2

84

Sample Input 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

Sample Output 3

3595