O - Maximum Score of a Playlist Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 533 点

問題文

高橋君は、音楽プレイリストを作成しようとしています。候補となる楽曲が N 曲あり、それぞれ 1 から N の番号が付けられています。楽曲は決まった順番でリストに並んでおり、高橋君はこの中から 部分列（元の順序を保ったまま 1 曲以上を選ぶ）を 1 つ選んでプレイリストを作ります。

各楽曲 i には「単体スコア」 A_i と「相性値」 B_i の 2 つのパラメータがあります。

選んだ部分列を c_1, c_2, \ldots, c_k としたとき、そのプレイリストの「総合スコア」は以下のように定義されます。

  • k = 1 のとき、総合スコアは A_{c_1} です。
  • k \geq 2 のとき、総合スコアは \displaystyle A_{c_1} + \sum_{j=2}^{k} (A_{c_j} + B_{c_{j-1}} \times B_{c_j}) です。

すなわち、プレイリスト内で連続して再生される 2 曲 c_{j-1} と c_j の間には、それぞれの相性値の積 B_{c_{j-1}} \times B_{c_j} がボーナスとして加算されます。さらに、選ばれた全楽曲の単体スコアの合計も加算されます。

すべての可能な部分列の中から、総合スコアが最大となるものを見つけ、その最大値を求めてください。

制約

  • 1 \leq N \leq 10^5
  • -10^6 \leq A_i \leq 10^6
  • -10^6 \leq B_i \leq 10^6
  • 入力はすべて整数である。
  • この制約のもとで、総合スコアの最大値は符号付き 64 bit 整数に収まる。

入力

N
A_1 B_1
A_2 B_2
:
A_N B_N
  • 1 行目には、楽曲の数を表す N が与えられる。
  • 2 行目から N + 1 行目では、各楽曲のパラメータが与えられる。
  • 1 + i 行目では、楽曲 i の単体スコア A_i と相性値 B_i がスペース区切りで与えられる。

出力

総合スコアの最大値を 1 行で出力してください。

入力例 1

4
3 2
-1 4
5 -1
2 3

出力例 1

24

入力例 2

5
-5 10
4 -10
-2 10
3 -10
1 10

出力例 2

194

入力例 3

10
7 3
-4 -2
10 5
-8 1
6 -3
2 4
-1 -5
9 2
-6 6
5 -1

出力例 3

77

入力例 4

30
120 15
-300 -20
45 7
80 12
-50 -9
200 25
-150 5
60 -30
90 -4
-20 18
300 10
-400 -15
110 22
75 -11
-90 8
130 -25
-60 14
250 3
-10 -19
95 27
-200 6
180 -8
40 16
-70 -22
220 13
-30 2
55 -17
160 21
-120 -6
100 9

出力例 4

4517

入力例 5

1
-1000000 -1000000

出力例 5

-1000000

Score : 533 pts

Problem Statement

Takahashi is planning to create a music playlist. There are N candidate songs, numbered 1 to N. The songs are arranged in a fixed order, and Takahashi will choose a subsequence (selecting one or more songs while preserving their original order) to create the playlist.

Each song i has two parameters: a "single score" A_i and a "compatibility value" B_i.

If the chosen subsequence of songs is c_1, c_2, \ldots, c_k, the "total score" of the playlist is defined as follows:

  • When k = 1, the total score is A_{c_1}.
  • When k \geq 2, the total score is \displaystyle A_{c_1} + \sum_{j=2}^{k} (A_{c_j} + B_{c_{j-1}} \times B_{c_j}).

In other words, a bonus of B_{c_{j-1}} \times B_{c_j} (the product of their compatibility values) is added between any two consecutive songs c_{j-1} and c_j in the playlist. In addition, the sum of the single scores of all chosen songs is added.

Find the maximum possible total score among all possible subsequences.

Constraints

  • 1 \leq N \leq 10^5
  • -10^6 \leq A_i \leq 10^6
  • -10^6 \leq B_i \leq 10^6
  • All input values are integers.
  • Under these constraints, the maximum total score fits within a signed 64-bit integer.

Input

N
A_1 B_1
A_2 B_2
:
A_N B_N
  • The first line contains N, the number of songs.
  • The next N lines, from the 2nd to the (N+1)-th line, contain the parameters of each song.
  • The (1+i)-th line contains the single score A_i and the compatibility value B_i of song i, separated by a space.

Output

Print the maximum total score on a single line.

Sample Input 1

4
3 2
-1 4
5 -1
2 3

Sample Output 1

24

Sample Input 2

5
-5 10
4 -10
-2 10
3 -10
1 10

Sample Output 2

194

Sample Input 3

10
7 3
-4 -2
10 5
-8 1
6 -3
2 4
-1 -5
9 2
-6 6
5 -1

Sample Output 3

77

Sample Input 4

30
120 15
-300 -20
45 7
80 12
-50 -9
200 25
-150 5
60 -30
90 -4
-20 18
300 10
-400 -15
110 22
75 -11
-90 8
130 -25
-60 14
250 3
-10 -19
95 27
-200 6
180 -8
40 16
-70 -22
220 13
-30 2
55 -17
160 21
-120 -6
100 9

Sample Output 4

4517

Sample Input 5

1
-1000000 -1000000

Sample Output 5

-1000000