← 返回题目列表

AtCoder · arc213_a

A. 交换游戏

中文机器翻译题面 查看原题

分数: 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 按照此顺序,您将执行以下操作:

  1. 首先,对中的两个相邻元素执行零次或一次交换 A.
    • 具体来说,“交换两个相邻元素 A”表示选择 j 与 1 \le j \le L-1,并交换 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,所以 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