[ABC219H] Candles

在一条数轴上有 $N$ 支蜡烛，第 $i$ 支蜡烛长度为 $A_i$，且位于数轴上的 $X_i$ 处。 时刻 $0$ 时，$N$ 支蜡烛都被点燃。一根点燃的蜡烛每过一时刻就会减少 $1$ 的长度。当长度变为 $0$ 时蜡烛将会熄灭。熄灭的蜡烛的长度不会减少。 时刻 $0$ 时，你位于数轴上的 $0$ 处。一时刻中你可以在数轴上左右移动不超过 $1$ 的单位距离。当你到达某支蜡烛所在的位置时，你可以选择熄灭这支蜡烛，熄灭蜡烛的时间忽略不计。如果有多支蜡烛位于同一个位置，你可以一次性熄灭该位置上的所有蜡烛。 求时刻 $10^{100}$ 时最大的蜡烛总长度。

[problemUrl]: https://atcoder.jp/contests/abc219/tasks/abc219_h 無限に伸びる数直線の上に $ N $ 本のろうそくが置かれています。 $ i $ 番目のろうそくは座標 $ X_i $ にあり、時刻 $ 0 $ には長さは $ A_i $ で、火がついています。 火のついたろうそくは $ 1 $ 分あたり長さが $ 1 $ 短くなり、長さが $ 0 $ になると燃え尽きてそれ以降長さは変わりません。また、火を消されたろうそくの長さは変わりません。 高橋君は時刻 $ 0 $ に座標 $ 0 $ にいて、毎分 $ 1 $ 以下の距離を移動することができます。高橋君は自分がいる座標と同じ座標にろうそくがある場合、そのろうそくの火を消すことができます。（同じ座標に複数ある場合はまとめて消すことができます。）ここで、ろうそくの火を消すのにかかる時間は無視できます。 高橋君が適切に行動したとき、時刻 $ 0 $ から $ 10^{100} $ 分後に残っているろうそくの長さの総和としてあり得る最大の値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ X_1 $ $ A_1 $ $ X_2 $ $ A_2 $ $ : $ $ X_N $ $ A_N $

答えを出力せよ。

3
-2 10
3 10
12 10

11

5
0 1000000000
0 1000000000
1 1000000000
2 1000000000
3 1000000000

4999999994

### 制約 - $ 1\ \leq\ N\ \leq\ 300 $ - $ -10^9\ \leq\ X_i\ \leq\ 10^9 $ - $ 1\ \leq\ A_i\ \leq\ 10^9 $ - 入力は全て整数である。 ### Sample Explanation 1 $ 3 $ 番目のろうそくは座標 $ 12 $ にあるため、高橋君の行動に関わらず火を消すより先に燃え尽きてしまいます。 残りの $ 2 $ 本について、まず座標 $ -2 $ へ $ 2 $ 分かけて移動して $ 1 $ 本目のろうそくの火を消し、その後 $ 5 $ 分かけて座標 $ 3 $ へ移動して $ 2 $ 本目のろうそくの火を消すと、これ以降ろうそくの長さが変化することはありません。 それぞれのろうそくの長さは $ 10-2=8 $ と $ 10-2-5=3 $ 残り、このとき残った長さの総和は $ 8+3=11 $ となって、このときが最大です。 よって、 $ 11 $ を出力します。 ### Sample Explanation 2 同じ座標に $ 2 $ つ以上のろうそくが存在する可能性があること、答えが $ 32 $ bit整数に収まらないことがあることに注意してください。