AT_ndpc2026_o ゲーム

你将要玩一个游戏。这个游戏持续 $N$ 天。每天你可以选择一个整数 $x \in \{0,1,2\}$，支付 $x$ 日元，并执行第 $x$ 个动作。如果你在第 $i$ 天执行了动作 $x$，你将获得 $A_{i,x}$ 点经验值。每一天只能选择并执行一个动作。 现在给定 $Q$ 个询问。每个询问给定一对整数 $(d, b)$，其中 $1 \leq d \leq N$ 且 $0 \leq b \leq 2d$。请你解决以下问题： - 假设你从第 $1$ 天到第 $d$ 天，总共花费恰好 $b$ 日元。那么，在这 $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$ 分。 ### 样例说明 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$ 点经验。 # 约束条件 - $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$ - 所有输入值均为整数。 由 ChatGPT 5 翻译