AT_arc213_a.[ARC213A] Swapping Game

给定 $N$ 个关于 $1 \sim L$ 的排列，第 $i$ 个排列为 $P_i$，第 $i$ 个的第 $j$ 项为 $P_{i, j}$。

你有一个排列 $A$，它初始是 $(1, 2, \cdots, L)$。你最开始有 $0$ 日元。接下来，你将进行 $N$ 次操作。每次操作你可以交换相邻两项的值。在第 $i$ 次操作后如果 $A = P_i$ 则你获得 $C_i$ 日元。问 $N$ 次操作后的最大金额。

输入格式如下：

$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 解释

下面的操作可以让你获得 $600$ 日元：

• $i = 1$。交换 $A_1$ 和 $A_2$。此时 $A = (2, 1, 3)$。因为 $A = P_1$，你获得了 $200$ 日元。
• $i = 2$。交换 $A_2$ 和 $A_3$。此时 $A = (2, 3, 1)$。因为 $A \neq P_2$，你没有获得日元。
• $i = 3$。不交换。此时 $A = (2, 3, 1)$。因为 $A = P_3$，你获得了 $300$ 日元。
• $i = 4$。交换 $A_1$ 和 $A_2$。此时 $A = (3, 2, 1)$。因为 $A = P_4$，你获得了 $100$ 日元。

数据范围

• $1 \le N \le 3 \times 10^4$。
• $1 \le L \le 9$。
• $0 \le C_i \le 10^4$
• 对于 $1 \le i \le N$，保证 $P_i$ 是 $1 \sim L$ 的排列。
• 输入一定是整数。