AT_ndpc2026_o ゲーム

You are going to play a game. The game consists of actions over $ N $ days. Each day, you choose an integer $ x \in {0,1,2} $ , pay $ x $ yen, and perform action $ x $ . If you perform action $ x $ on day $ i $ , you gain $ A_{i,x} $ experience points. You cannot perform more than one action per day. You are given $ Q $ queries. In each query, you are given a pair of integers $ (d, b) $ such that $ 1 \leq d \leq N $ and $ 0 \leq b \leq 2d $ . Solve the following problem: - Suppose you spend exactly $ b $ yen in total from day $ 1 $ to day $ d $ . What is the maximum possible total experience you can gain during these $ d $ days? You are given $ T $ test cases. Solve each of them.

The input is given from standard input in the following format: > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ Each test case is given in the following format: > $ 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 $ Each query is given in the following format: > $ d $ $ b $

Output the answers for all test cases in order. For each test case, print $ Q $ lines. On the $ i $ -th line, output the answer to the $ i $ -th query.

### Partial Score This problem has partial scoring. - If all queries satisfy $ d = N $ , you will get $ 5 $ points. ### Sample Explanation 1 For example, consider the $ 3 $ -rd query of the first test case: $ d=3, b=3 $ . You can achieve a total experience of $ 18 $ in the following way, which is optimal: - Day $ 1 $ : choose $ x=0 $ . Pay $ 0 $ yen and gain $ A_{1,0}=1 $ experience. - Day $ 2 $ : choose $ x=1 $ . Pay $ 1 $ yen and gain $ A_{2,1}=8 $ experience. - Day $ 3 $ : choose $ x=2 $ . Pay $ 2 $ yen and gain $ A_{3,2}=9 $ experience. ### 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 $ - The sum of $ N $ over all test cases is at most $ 2.5 \times 10^5 $ - The sum of $ Q $ over all test cases is at most $ 10^4 $ - All input values are integers