A - Swapping Game Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 600 点

問題文

(1,2, \dots ,L) の順列が N 個あります。i (1 \le i \le N) 個目の順列は P_i であり、P_i の j (1 \le j \le L) 番目の要素は P_{i,j} です。

はじめ、あなたは A = (1,2, \dots ,L) を持っており、所持金は 0 円です。これから、i = 1,2, \dots ,N の順に以下の操作を行います。

  1. まず、A の隣接 2 項の swap を 0 回または 1 回行う。
    • 「A の隣接 2 項の swap」とは、1 \le j \le L-1 なる j を選び、A_j と A_{j+1} を入れ替える操作を指します。
  2. その後、A = P_i となっていれば C_i 円を獲得する。

最終的なあなたの所持金としてありえる金額の最大値を求めて下さい。

制約

  • 1 \leq N \leq 3 \times 10^4
  • 1 \leq L \leq 9
  • 0 \leq C_i \leq 10^4
  • P_i は (1,2, \dots, L) の順列
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N L
C_1 P_{1,1} P_{1,2} \dots P_{1,L}
C_2 P_{2,1} P_{2,2} \dots P_{2,L}
\vdots
C_N P_{N,1} P_{N,2} \dots P_{N,L}

出力

答えを出力せよ。

入力例 1

4 3
200 2 1 3
400 3 1 2
300 2 3 1
100 3 2 1

出力例 1

600

以下のように操作を行うことで所持金を 600 円にすることが出来ます。

  • i=1 : A_1,A_2 を swap し、A=(2,1,3) とする。A=P_1 であるため、200 円を獲得する。
  • i=2 : A_2,A_3 を swap し、A=(2,3,1) とする。A=P_2 でない。
  • i=3 : swap を行わず、A=(2,3,1) のままとする。A=P_3 であるため、300 円を獲得する。
  • i=4 : A_1,A_2 を swap し、A=(3,2,1) とする。A=P_4 であるため、100 円を獲得する。

入力例 2

2 1
0 1
10000 1

出力例 2

10000

入力例 3

1 9
2025 2 4 6 8 7 5 1 9 3

出力例 3

0

入力例 4

10 5
2615 5 1 3 4 2
4275 1 3 2 5 4
4331 3 1 5 2 4
1457 3 5 1 2 4
2222 1 3 2 4 5
5051 2 4 5 3 1
1082 2 3 1 5 4
1579 4 1 5 2 3
2855 5 1 3 2 4
5848 2 4 3 1 5

出力例 4

12345

Score : 600 points

Problem Statement

There are N permutations of (1,2,\dots,L). The i-th permutation is P_i, and the j-th element of P_i is P_{i,j} (1 \le j \le L).

Initially, you have A = (1,2,\dots,L), and your initial amount of money is 0 yen. From now on, for i = 1,2,\dots,N in this order, you will perform the following operation:

  1. First, perform zero or one swap of two adjacent elements in A.
    • Specifically, “a swap of two adjacent elements in A” means choosing j with 1 \le j \le L-1, and swapping A_j and A_{j+1}.
  2. Then, if A is equal to P_i, you gain C_i yen.

Find the maximum possible amount of money you can have at the end.

Constraints

  • 1 \leq N \leq 3 \times 10^4
  • 1 \leq L \leq 9
  • 0 \leq C_i \leq 10^4
  • Each P_i is a permutation of (1,2,\dots,L).
  • All input values are integers.

Input

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

N L
C_1 P_{1,1} P_{1,2} \dots P_{1,L}
C_2 P_{2,1} P_{2,2} \dots P_{2,L}
\vdots
C_N P_{N,1} P_{N,2} \dots P_{N,L}

Output

Print the answer.

Sample Input 1

4 3
200 2 1 3
400 3 1 2
300 2 3 1
100 3 2 1

Sample Output 1

600

By doing the operations as follows, you can end up with 600 yen.

  • For i=1: swap A_1 and A_2, so A=(2,1,3). We have A=P_1, so you gain 200 yen.
  • For i=2: swap A_2 and A_3, so A=(2,3,1). We have A \neq P_2.
  • For i=3: do not swap, so A=(2,3,1). We have A=P_3, so you gain 300 yen.
  • For i=4: swap A_1 and A_2, so A=(3,2,1). We have A=P_4, so you gain 100 yen.

Sample Input 2

2 1
0 1
10000 1

Sample Output 2

10000

Sample Input 3

1 9
2025 2 4 6 8 7 5 1 9 3

Sample Output 3

0

Sample Input 4

10 5
2615 5 1 3 4 2
4275 1 3 2 5 4
4331 3 1 5 2 4
1457 3 5 1 2 4
2222 1 3 2 4 5
5051 2 4 5 3 1
1082 2 3 1 5 4
1579 4 1 5 2 3
2855 5 1 3 2 4
5848 2 4 3 1 5

Sample Output 4

12345