题目描述

有三个长度为 $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$ 个测试用例。

约束条件

• $1 \\leq T \\leq 2 \\times 10^5$
• $1 \\leq N \\leq 2 \\times 10^5$
• 单个文件中 $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$
• 输入中的所有值均为整数。

输入

从标准输入获得输入数据，输入格式如下：

$T$ Case1 $\vdots$ CaseT

每个测试用例的格式如下：

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

输出

打印 $T$ 行。第 $i$ 行 $(1 \\leq i \\leq T)$ 应包含第 $i$ 个测试用例的答案。

示例输入 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

在第一个测试用例中，我们有：

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