题目描述

長さ $M$ の整数列 $A,\ B,\ C$ があります。

$C$ は整数 $x_1,\ \dots,\ x_N,\ y_1,\ \dots,\ y_N$ によって表されます。$C$ の先頭 $y_1$ 項は $x_1$ であり、続く $y_2$ 項は $x_2$ であり、$\ldots$、末尾の $y_N$ 項は $x_N$ です。

$B$ は $ B_i\ =\ \sum_{k\ =\ 1}^i\ C_k\ \,\ (1\ \leq\ i\ \leq\ M) $ によって定められます。

$A$ は $ A_i\ =\ \sum_{k\ =\ 1}^i\ B_k\ \,\ (1\ \leq\ i\ \leq\ M) $ によって定められます。

$A_1,\ \dots,\ A_M$ の最大値を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$T$ $\mathrm{case}_1$ $\vdots$ $\mathrm{case}_T$

各テストケースは以下の形式で与えられる。

$N$ $M$ $x_1$ $y_1$ $\vdots$ $x_N$ $y_N$

输出格式

$T$ 行出力せよ。$i\ \,\ (1\ \leq\ i\ \leq\ T)$ 行目には、$i$ 個目のテストケースに対する答えを出力せよ。

题目大意

题目描述

有三个数列 $A,B,C$。

其中 $C$ 表示为 $x_1,\ \dots,\ x_N,\ y_1,\ \dots,\ y_N$ 的形式，意思是前 $y_1$ 个数为 $x_1$,之后 $y_2$ 个数为 $x_2$……最后 $y_N$ 个数为 $x_N$。

$B$ 为 $C$ 的前缀和数组。

$A$ 为 $B$ 的前缀和数组。

求 $A$ 中最大值。

输入格式

对于每组数据，

第一行为两个数 $N$ 和 $M$，

第 $2$ 至 $N+1$ 行，第 $i$ 行为两个数 $x_{i-1}$ 和 $y_{i-1}$。

输出格式

对于每组数据，输出一行一个整数表示答案

样例 #1

样例输入 #1

3
3 7
-1 2
2 3
-3 2
10 472
-4 12
1 29
2 77
-1 86
0 51
3 81
3 17
-2 31
-4 65
4 23
1 1000000000
4 1000000000

样例输出 #1

4
53910
2000000002000000000

提示

数据范围

• $1\ \leq\ T\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $\sum\ N\ \leq\ 2\times\ 10^5$
• $1\ \leq\ M\ \leq\ 10^9$
• $|x_i|\ \leq\ 4\ \,\ (1\ \leq\ i\ \leq\ N)$
• $y_i\ \gt\ 0\ \,\ (1\ \leq\ i\ \leq\ N)$
• $\sum_{k\ =\ 1}^N\ y_k\ =\ M$

3
3 7
-1 2
2 3
-3 2
10 472
-4 12
1 29
2 77
-1 86
0 51
3 81
3 17
-2 31
-4 65
4 23
1 1000000000
4 1000000000

4
53910
2000000002000000000

提示

制約

• $1\ \leq\ T\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1$ つのファイルに含まれるテストケースについて、$N$ の総和は $2\ \times\ 10^5$ 以下
• $1\ \leq\ M\ \leq\ 10^9$
• $|x_i|\ \leq\ 4\ \,\ (1\ \leq\ i\ \leq\ N)$
• $y_i\ \gt\ 0\ \,\ (1\ \leq\ i\ \leq\ N)$
• $\sum_{k\ =\ 1}^N\ y_k\ =\ M$
• 入力は全て整数

Sample Explanation 1

$1$ つ目のテストケースにおいて、 - $C\ =\ (-1,\ -1,\ 2,\ 2,\ 2,\ -3,\ -3)$ - $B\ =\ (-1,\ -2,\ 0,\ 2,\ 4,\ 1,\ -2)$ - $A\ =\ (-1,\ -3,\ -3,\ -1,\ 3,\ 4,\ 2)$ であるので、$A_1,\ \dots,\ A_M$ の最大値は $4$ です。