题目描述

你要进行一个持续 $N$ 天的游戏。每天选择一个整数 $x\in\{0,1,2\}$，支付 $x$ 日元并执行行动 $x$。如果在第 $i$ 天执行行动 $x$，就能获得 $A_{i,x}$ 点经验值。每天只能执行一次行动。

回答 $Q$ 个询问。每个询问给出整数对 $(d,b)$，满足 $1\le d\le N$ 且 $0\le b\le 2d$。假设从第 $1$ 天到第 $d$ 天支付的总金额恰好为 $b$ 日元，求这 $d$ 天内能够获得的最大经验值总和。

共有 $T$ 组测试数据，请分别求解。

限制条件

• $1\le T\le 10^4$
• $1\le N\le 2.5\times 10^5$
• $1\le Q\le 10^4$
• $0\le A_{i,x}\le 10^9$
• $1\le d\le N$
• $0\le b\le 2d$
• 所有测试数据中 $N$ 的总和不超过 $2.5\times 10^5$。
• 所有测试数据中 $Q$ 的总和不超过 $10^4$。
• 所有输入均为整数。

部分分

• 对所有询问都满足 $d=N$ 的数据求解正确，可获得 $5$ 分。

输入

T
case_1
case_2
...
case_T

每组测试数据的格式如下：

N Q
A_{1,0} A_{1,1} A_{1,2}
A_{2,0} A_{2,1} A_{2,2}
...
A_{N,0} A_{N,1} A_{N,2}
d_1 b_1
d_2 b_2
...
d_Q b_Q

输出

按照测试数据给出的顺序输出所有答案。对于每组测试数据，输出 $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$ 个询问为 $d=3,b=3$。以下选择可以获得最大总经验值 $18$：

• 第 $1$ 天选择 $x=0$，获得 $A_{1,0}=1$ 点经验；
• 第 $2$ 天选择 $x=1$，获得 $A_{2,1}=8$ 点经验；
• 第 $3$ 天选择 $x=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