H - Candles Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600600

問題文

無限に伸びる数直線の上に NN 本のろうそくが置かれています。 ii 番目のろうそくは座標 XiX_i にあり、時刻 00 には長さは AiA_i で、火がついています。 火のついたろうそくは 11 分あたり長さが 11 短くなり、長さが 00 になると燃え尽きてそれ以降長さは変わりません。また、火を消されたろうそくの長さは変わりません。

高橋君は時刻 00 に座標 00 にいて、毎分 11 以下の距離を移動することができます。高橋君は自分がいる座標と同じ座標にろうそくがある場合、そのろうそくの火を消すことができます。(同じ座標に複数ある場合はまとめて消すことができます。)ここで、ろうそくの火を消すのにかかる時間は無視できます。

高橋君が適切に行動したとき、時刻 00 から 1010010^{100} 分後に残っているろうそくの長さの総和としてあり得る最大の値を求めてください。

制約

  • 1N3001 \leq N \leq 300
  • 109Xi109-10^9 \leq X_i \leq 10^9
  • 1Ai1091 \leq A_i \leq 10^9
  • 入力は全て整数である。

入力

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

NN
X1X_1 A1A_1
X2X_2 A2A_2
::
XNX_N ANA_N

出力

答えを出力せよ。


入力例 1Copy

Copy
3
-2 10
3 10
12 10

出力例 1Copy

Copy
11

33 番目のろうそくは座標 1212 にあるため、高橋君の行動に関わらず火を消すより先に燃え尽きてしまいます。
残りの 22 本について、まず座標 2-222 分かけて移動して 11 本目のろうそくの火を消し、その後 55 分かけて座標 33 へ移動して 22 本目のろうそくの火を消すと、これ以降ろうそくの長さが変化することはありません。 それぞれのろうそくの長さは 102=810-2=81025=310-2-5=3 残り、このとき残った長さの総和は 8+3=118+3=11 となって、このときが最大です。 よって、 1111 を出力します。


入力例 2Copy

Copy
5
0 1000000000
0 1000000000
1 1000000000
2 1000000000
3 1000000000

出力例 2Copy

Copy
4999999994

同じ座標に 22 つ以上のろうそくが存在する可能性があること、答えが 3232 bit整数に収まらないことがあることに注意してください。

Score : 600600 points

Problem Statement

There are NN candles on an infinite number line. The ii-th candle is at the coordinate XiX_i. At time 00, it has a length of AiA_i and is lit. Each minute, the length of a lit candle decreases by 11. When the length becomes 00, it burns out, and its length does not change after that. Additionally, the length of an unlit candle does not change.

Takahashi is at the coordinate 00 at time 00. Each minute, he can move a distance of at most 11. If there is a candle at his current coordinate, he can put out that candle. (If there are multiple candles there, he can put out all of them.) The time it takes to put out a candle is negligible.

Find the maximum possible total length of the candles remaining at 1010010^{100} minutes after time 00, achieved by Takahashi's optimal course of actions.

Constraints

  • 1N3001 \leq N \leq 300
  • 109Xi109-10^9 \leq X_i \leq 10^9
  • 1Ai1091 \leq A_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

NN
X1X_1 A1A_1
X2X_2 A2A_2
::
XNX_N ANA_N

Output

Print the answer.


Sample Input 1Copy

Copy
3
-2 10
3 10
12 10

Sample Output 1Copy

Copy
11

The third candle, which is at coordinate 1212, will burn out before Takahashi puts it out, regardless of Takahashi's behavior.
For the other two candles, if he goes to coordinate 2-2 in two minutes to put out the first and then goes to coordinate 33 in five minutes to put out the second, the lengths of those candles will not change after that. The lengths of those candles remaining are 102=810-2=8 and 1025=310-2-5=3, for a total of 8+3=118+3=11, which is the maximum that can be achieved. Thus, print 1111.


Sample Input 2Copy

Copy
5
0 1000000000
0 1000000000
1 1000000000
2 1000000000
3 1000000000

Sample Output 2Copy

Copy
4999999994

Note that two or more candles may occupy the same coordinate and that the answer may not fit into a 3232-bit integer.



2025-04-28 (Mon)
04:24:00 +00:00