Swapping Game

AtCoder

IDarc213_a

Time2000ms

Memory256MB

Difficulty—

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}$ [samples]

Samples

Input #1

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.

Input #2

2 1
0 1
10000 1

Output #2

Input #3

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

Output #3

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

Output #4

API Response (JSON)

{
  "problem": {
    "name": "Swapping Game",
    "description": {
      "content": "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 init",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc213_a"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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$).\nInitially, you have $A = (1,2,\\dots,L)$, and your init...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments