题目描述

無限に伸びる数直線の上に $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$

输出格式

答えを出力せよ。

题目大意

$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整数に収まらないことがあることに注意してください。