当前没有测试数据。

F - Sum Sum Max

分数: 500分

问题描述

有三个长度为$M$的整数序列$A, B, C$。

通过整数$x_1, \dots, x_N, y_1, \dots, y_N$表示$C$。$C$的前$y_1$个元素为$x_1$，接下来的$y_2$个元素为$x_2$，依次类推，最后的$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$

$\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$个测试样例的答案。

---

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