AT_ndpc2026_o ゲーム

あなたはゲームをすることにしました。ゲームは $ N $ 日間の行動からなります。あなたは毎日整数 $ x \in \lbrace 0,1,2 \rbrace $ を $ 1 $ つ選び、 $ x $ 円を支払って行動 $ x $ を行います。 $ i $ 日目に行動 $ x $ を行うと $ A_{i,x} $ の経験値を得ます。 $ 1 $ 日に複数回行動を行うことは出来ません。 $ Q $ 個のクエリに答えてください。クエリでは $ 1 \leq d \leq N, 0 \leq b \leq 2d $ を満たす整数の組 $ (d,b) $ が与えられるので、次の問題を解いてください。 - $ 1 $ 日目から $ d $ 日目までに合計でちょうど $ b $ 円支払ったとする。この時、 $ 1 $ 日目から $ d $ 日目までに得た経験値の総和としてあり得る最大値を求めよ。 $ T $ 個のテストケースが与えられるので、それぞれについて問題を解いてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ Q $ $ A_{1,0} $ $ A_{1,1} $ $ A_{1,2} $ $ A_{2,0} $ $ A_{2,1} $ $ A_{2,2} $ $ \vdots $ $ A_{N,0} $ $ A_{N,1} $ $ A_{N,2} $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ 各クエリは以下の形式で与えられる。 > $ d $ $ b $

各テストケースの答えをテストケースが与えられた順に出力せよ。 各テストケースでは $ Q $ 行出力せよ。 $ i $ 行目には $ i $ 番目のクエリへの答えを出力せよ。

### 部分点 この問題には部分点が設定されている。 - 全てのクエリに対して $ d = N $ が成り立つデータセットに正解した場合、 $ 5 $ 点が与えられる。 ### Sample Explanation 1 例えば $ 1 $ 番目のテストケースの $ 3 $ 番目のクエリを考えます。 $ d=3,b=3 $ です。 このとき、以下の方法で合計 $ 18 $ の経験値を得ることが出来て、これが最大です。 - $ 1 $ 日目： $ x=0 $ を選ぶ。 $ 0 $ 円支払って $ A_{1,0}=1 $ の経験値を得る。 - $ 2 $ 日目： $ x=1 $ を選ぶ。 $ 1 $ 円支払って $ A_{2,1}=8 $ の経験値を得る。 - $ 3 $ 日目： $ x=2 $ を選ぶ。 $ 2 $ 円支払って $ A_{3,2}=9 $ の経験値を得る。 ### Constraints - $ 1 \leq T \leq 10^4 $ - $ 1 \leq N \leq 2.5 \times 10^5 $ - $ 1 \leq Q \leq 10^4 $ - $ 0 \leq A_{i,x} \leq 10^9 $ - $ 1 \leq d \leq N $ - $ 0 \leq b \leq 2d $ - 全てのテストケースに対する $ N $ の総和は $ 2.5 \times 10^5 $ 以下 - 全てのテストケースに対する $ Q $ の総和は $ 10^4 $ 以下 - 入力される値は全て整数