分数: 7 点
问题陈述
你要玩一个游戏。游戏由以下动作组成 N 天。每天,您选择一个整数 x \in {0,1,2},支付 x 日元,并执行操作 x。如果您执行操作 x 当天 i,你获得 A_{i,x} 经验值。您每天不能执行一项以上的操作。
你被给予 Q 查询。在每个查询中,都会给出一对整数 (d, b) 这样 1 \leq d \leq N 和 0 \leq b \leq 2d。解决以下问题:
- 假设您花费了 b 当天总计日元 1 到今天 d。在这些过程中您可以获得的最大可能总经验是多少 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
例如,考虑 3-第一个测试用例的rd查询: 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