{"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 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:\n\n1.  First, perform zero or one swap of two adjacent elements in $A$.\n    *   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}$.\n2.  Then, if $A$ is equal to $P_i$, you gain $C_i$ yen.\n\nFind the maximum possible amount of money you can have at the end.\n\n## Constraints\n\n*   $1 \\leq N \\leq 3 \\times 10^4$\n*   $1 \\leq L \\leq 9$\n*   $0 \\leq C_i \\leq 10^4$\n*   Each $P_i$ is a permutation of $(1,2,\\dots,L)$.\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $L$\n$C_1$ $P_{1,1}$ $P_{1,2}$ $\\dots$ $P_{1,L}$\n$C_2$ $P_{2,1}$ $P_{2,2}$ $\\dots$ $P_{2,L}$\n$\\vdots$\n$C_N$ $P_{N,1}$ $P_{N,2}$ $\\dots$ $P_{N,L}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc213_a","tags":[],"sample_group":[["4 3\n200 2 1 3\n400 3 1 2\n300 2 3 1\n100 3 2 1","600\n\nBy doing the operations as follows, you can end up with $600$ yen.\n\n*   For $i=1$: swap $A_1$ and $A_2$, so $A=(2,1,3)$. We have $A=P_1$, so you gain $200$ yen.\n*   For $i=2$: swap $A_2$ and $A_3$, so $A=(2,3,1)$. We have $A \\neq P_2$.\n*   For $i=3$: do not swap, so $A=(2,3,1)$. We have $A=P_3$, so you gain $300$ yen.\n*   For $i=4$: swap $A_1$ and $A_2$, so $A=(3,2,1)$. We have $A=P_4$, so you gain $100$ yen."],["2 1\n0 1\n10000 1","10000"],["1 9\n2025 2 4 6 8 7 5 1 9 3","0"],["10 5\n2615 5 1 3 4 2\n4275 1 3 2 5 4\n4331 3 1 5 2 4\n1457 3 5 1 2 4\n2222 1 3 2 4 5\n5051 2 4 5 3 1\n1082 2 3 1 5 4\n1579 4 1 5 2 3\n2855 5 1 3 2 4\n5848 2 4 3 1 5","12345"]],"created_at":"2026-03-03 11:01:13"}}