配点 : $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$

出力

答えを出力せよ。

3
-2 10
3 10
12 10

11

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

5
0 1000000000
0 1000000000
1 1000000000
2 1000000000
3 1000000000

4999999994

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