AT_arc213_a [ARC213A] Swapping Game

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.

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} $

Print the answer.

### Sample Explanation 1 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. ### 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.