分数: 600 点
问题陈述
有 N 的排列 (1,2,\dots,L)。的 团队的 i-th 排列是 P_i,以及 j- 第一个元素 P_i is P_{i,j} (1 \le j \le L).
最初,您有 A = (1,2,\dots,L),您的初始金额是 0 日元。从现在开始,为了 i = 1,2,\dots,N 按照此顺序,您将执行以下操作:
- 首先,对中的两个相邻元素执行零次或一次交换 A.
- 具体来说,“交换两个相邻元素 A”表示选择 j 与 1 \le j \le L-1,并交换 A_j 和 A_{j+1}.
- 那么,如果 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,所以 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 日元。
示例输入 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