AT_ndpc2026_o.Game

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.

你将进行一场游戏。游戏持续 $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$ 组测试数据，请对每组数据求解。

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$

输入从标准输入中按以下格式给出：

$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$

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.

按顺序输出所有测试用例的答案。
对于每个测试用例，输出 $Q$ 行。在第 $i$ 行输出第 $i$ 个查询的答案。

Partial Score

This problem has partial scoring.

• If all queries satisfy $d = N$, you will get $5$ points.

Sample 1 Explanation:
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

部分得分

本题采用部分得分制。

• 若所有查询均满足 $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$
• 所有输入值均为整数