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.