和的和的最大值

题目描述

有三个长度均为 $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 \le i \le M)$。

$A$ 定义为 $A_i = \sum_{k = 1}^i B_k \, (1 \le i \le M)$。

求 $A_1, \dots, A_M$ 中的最大值。

你需要解决 $T$ 组测试用例。

输入格式

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

T
case_1
⋮
case_T

每个测试用例格式如下:

N M
x_1 y_1
⋮
x_N y_N

输出格式

输出 $T$ 行。第 $i$ 行 $(1 \le i \le T)$ 应包含第 $i$ 个测试用例的答案。

样例

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

在第一个测试用例中,有:

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

数据范围

• $1 \le T \le 2 \times 10^5$
• $1 \le N \le 2 \times 10^5$
• 单个文件中 $N$ 的总和至多为 $2 \times 10^5$。
• $1 \le M \le 10^9$
• $|x_i| \le 4 \, (1 \le i \le N)$
• $y_i \gt 0 \, (1 \le i \le N)$
• $\sum_{k = 1}^N y_k = M$
• 输入中的所有值均为整数。