/ 
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 7 点
問題文
あなたはゲームをすることにしました。ゲームは 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 個のテストケースが与えられるので、それぞれについて問題を解いてください。
制約
- 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 以下
- 入力される値は全て整数
部分点
この問題には部分点が設定されている。
- 全てのクエリに対して d = N が成り立つデータセットに正解した場合、5 点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
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 番目のクエリへの答えを出力せよ。
入力例 1
2 3 3 1 3 2 4 8 1 1 6 9 1 1 2 3 3 3 5 5 45 58 82 47 39 94 36 54 74 80 61 95 61 57 69 2 4 5 7 4 1 5 5 3 0
出力例 1
3 10 18 176 387 226 371 128
例えば 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 の経験値を得る。
入力例 2
1 10 10 76 30 16 30 94 48 60 67 90 43 63 47 49 33 66 14 49 79 39 62 37 34 79 96 29 86 85 59 42 69 10 16 10 13 10 8 10 20 10 2 10 5 10 4 10 0 10 15 10 19
出力例 2
764 770 724 633 554 664 634 433 780 679
Score : 7 points
Problem Statement
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.
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
Partial Score
This problem has partial scoring.
- If all queries satisfy d = N, you will get 5 points.
Input
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
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.
Sample Input 1
2 3 3 1 3 2 4 8 1 1 6 9 1 1 2 3 3 3 5 5 45 58 82 47 39 94 36 54 74 80 61 95 61 57 69 2 4 5 7 4 1 5 5 3 0
Sample Output 1
3 10 18 176 387 226 371 128
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.
Sample Input 2
1 10 10 76 30 16 30 94 48 60 67 90 43 63 47 49 33 66 14 49 79 39 62 37 34 79 96 29 86 85 59 42 69 10 16 10 13 10 8 10 20 10 2 10 5 10 4 10 0 10 15 10 19
Sample Output 2
764 770 724 633 554 664 634 433 780 679