AT_arc213_a [ARC213A] Swapping Game

$ (1,2, \dots ,L) $ の順列が $ N $ 個あります。 $ i $ $ (1 \le i \le N) $ 個目の順列は $ P_i $ であり、 $ P_i $ の $ j $ $ (1 \le j \le L) $ 番目の要素は $ P_{i,j} $ です。 はじめ、あなたは $ A = (1,2, \dots ,L) $ を持っており、所持金は $ 0 $ 円です。これから、 $ i = 1,2, \dots ,N $ の順に以下の操作を行います。 1. まず、 $ A $ の隣接 $ 2 $ 項の swap を $ 0 $ 回または $ 1 $ 回行う。 - 「 $ A $ の隣接 $ 2 $ 項の swap」とは、 $ 1 \le j \le L-1 $ なる $ j $ を選び、 $ A_j $ と $ A_{j+1} $ を入れ替える操作を指します。 2. その後、 $ A = P_i $ となっていれば $ C_i $ 円を獲得する。 最終的なあなたの所持金としてありえる金額の最大値を求めて下さい。

入力は以下の形式で標準入力から与えられる。 > $ 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} $

答えを出力せよ。

### Sample Explanation 1 以下のように操作を行うことで所持金を $ 600 $ 円にすることが出来ます。 - $ i=1 $ : $ A_1,A_2 $ を swap し、 $ A=(2,1,3) $ とする。 $ A=P_1 $ であるため、 $ 200 $ 円を獲得する。 - $ i=2 $ : $ A_2,A_3 $ を swap し、 $ A=(2,3,1) $ とする。 $ A=P_2 $ でない。 - $ i=3 $ : swap を行わず、 $ A=(2,3,1) $ のままとする。 $ A=P_3 $ であるため、 $ 300 $ 円を獲得する。 - $ i=4 $ : $ A_1,A_2 $ を swap し、 $ A=(3,2,1) $ とする。 $ A=P_4 $ であるため、 $ 100 $ 円を獲得する。 ### Constraints - $ 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) $ の順列 - 入力はすべて整数