← 返回题目列表

AtCoder · abc240_f

I. 总和最大

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有整数序列 A, B, C 长度 M 每个。

C 用整数表示 x_1, \dots, x_N, y_1, \dots, y_N。第一个 y_1 条款 C 是 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
\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- 第一个测试用例。


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