F - Sum Sum Max Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

長さ 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
  • 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
  • 入力は全て整数

入力

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

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

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 です。

Score : 500 points

Problem Statement

There are integer sequences A, B, C of length M each.

C is represented by integers x_1, \dots, x_N, y_1, \dots, y_N. The first y_1 terms of C are x_1, the subsequent y_2 terms are x_2, \ldots, the last y_N terms are x_N.

B is defined by B_i = \sum_{k = 1}^i C_k \, (1 \leq i \leq M).

A is defined by A_i = \sum_{k = 1}^i B_k \, (1 \leq i \leq M).

Find the maximum value among A_1, \dots, A_M.

You will be given T test cases to solve.

Constraints

  • 1 \leq T \leq 2 \times 10^5
  • 1 \leq N \leq 2 \times 10^5
  • The sum of N in a single file is at most 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
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Each case is in the following format:

N M
x_1 y_1
\vdots
x_N y_N

Output

Print T lines. The i-th line (1 \leq i \leq T) should contain the answer to the i-th test case.

Sample Input 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

Sample Output 1

4
53910
2000000002000000000

In the first test case, we have:

  • C = (-1, -1, 2, 2, 2, -3, -3)
  • B = (-1, -2, 0, 2, 4, 1, -2)
  • A = (-1, -3, -3, -1, 3, 4, 2)

Thus, the maximum value among A_1, \dots, A_M is 4.