/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
無限に伸びる数直線の上に N 本のろうそくが置かれています。 i 番目のろうそくは座標 X_i にあり、時刻 0 には長さは A_i で、火がついています。 火のついたろうそくは 1 分あたり長さが 1 短くなり、長さが 0 になると燃え尽きてそれ以降長さは変わりません。また、火を消されたろうそくの長さは変わりません。
高橋君は時刻 0 に座標 0 にいて、毎分 1 以下の距離を移動することができます。高橋君は自分がいる座標と同じ座標にろうそくがある場合、そのろうそくの火を消すことができます。（同じ座標に複数ある場合はまとめて消すことができます。）ここで、ろうそくの火を消すのにかかる時間は無視できます。
高橋君が適切に行動したとき、時刻 0 から 10^{100} 分後に残っているろうそくの長さの総和としてあり得る最大の値を求めてください。
制約
- 1 \leq N \leq 300
- -10^9 \leq X_i \leq 10^9
- 1 \leq A_i \leq 10^9
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N X_1 A_1 X_2 A_2 : X_N A_N
出力
答えを出力せよ。
入力例 1
3 -2 10 3 10 12 10
出力例 1
11
3 番目のろうそくは座標 12 にあるため、高橋君の行動に関わらず火を消すより先に燃え尽きてしまいます。
残りの 2 本について、まず座標 -2 へ 2 分かけて移動して 1 本目のろうそくの火を消し、その後 5 分かけて座標 3 へ移動して 2 本目のろうそくの火を消すと、これ以降ろうそくの長さが変化することはありません。
それぞれのろうそくの長さは 10-2=8 と 10-2-5=3 残り、このとき残った長さの総和は 8+3=11 となって、このときが最大です。
よって、 11 を出力します。
入力例 2
5 0 1000000000 0 1000000000 1 1000000000 2 1000000000 3 1000000000
出力例 2
4999999994
同じ座標に 2 つ以上のろうそくが存在する可能性があること、答えが 32 bit整数に収まらないことがあることに注意してください。
Score : 600 points
Problem Statement
There are N candles on an infinite number line. The i-th candle is at the coordinate X_i. At time 0, it has a length of A_i and is lit. Each minute, the length of a lit candle decreases by 1. When the length becomes 0, 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 0 at time 0. Each minute, he can move a distance of at most 1. 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 10^{100} minutes after time 0, achieved by Takahashi's optimal course of actions.
Constraints
- 1 \leq N \leq 300
- -10^9 \leq X_i \leq 10^9
- 1 \leq A_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X_1 A_1 X_2 A_2 : X_N A_N
Output
Print the answer.
Sample Input 1
3 -2 10 3 10 12 10
Sample Output 1
11
The third candle, which is at coordinate 12, will burn out before Takahashi puts it out, regardless of Takahashi's behavior.
For the other two candles, if he goes to coordinate -2 in two minutes to put out the first and then goes to coordinate 3 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 10-2=8 and 10-2-5=3, for a total of 8+3=11, which is the maximum that can be achieved. Thus, print 11.
Sample Input 2
5 0 1000000000 0 1000000000 1 1000000000 2 1000000000 3 1000000000
Sample Output 2
4999999994
Note that two or more candles may occupy the same coordinate and that the answer may not fit into a 32-bit integer.