A - Range of Illumination Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君は、直線状の道路に設置された街灯の管理をしています。

道路は数直線として表され、街灯は原点の位置に設置されています。道路上には N 個の標識があり、i 番目の標識は座標 X_i の位置にあり、重要度 P_i を持っています。なお、同じ座標に複数の標識が存在することもあります。

高橋君は、街灯の照らす範囲を決める非負整数 R を 1 つ選びます。R を選ぶと、街灯は原点からの距離が R 以下の範囲、すなわち座標 -R 以上 R 以下の範囲を照らします。このとき、|X_i| \leq R を満たすすべての標識が照らされます。

一方、照明の電力コストとして R^2 がかかります。

照らされた標識の重要度の合計値から電力コスト R^2 を引いた値を「効果」と呼びます。すなわち、R を選んだときの効果は次のように定義されます。

\left(\sum_{|X_i| \leq R} P_i\right) - R^2

R = 0 を選んだ場合、電力コストは 0 であり、照らされるのは座標 0 にある標識のみです。座標 0 に標識が存在すれば効果はその重要度の合計（正の値）となり、存在しなければ効果は 0 となります。したがって、効果の最大値は常に 0 以上です。

高橋君が非負整数 R を最適に選んだとき、効果の最大値を求めてください。

制約

  • 1 \leq N \leq 100
  • -100 \leq X_i \leq 100
  • 1 \leq P_i \leq 100
  • X_i および P_i はすべて整数である

入力

N
X_1 P_1
X_2 P_2
\vdots
X_N P_N
  • 1 行目には、標識の数を表す整数 N が与えられる。
  • 続く N 行のうち i 行目には、i 番目の標識の座標 X_i と重要度 P_i がスペース区切りで与えられる。

出力

効果の最大値を 1 行で出力せよ。

入力例 1

3
1 10
-2 8
5 3

出力例 1

14

入力例 2

2
50 1
-50 1

出力例 2

0

入力例 3

10
0 5
1 10
-1 10
3 20
-3 20
5 15
-5 15
10 50
-10 50
7 30

出力例 3

125

入力例 4

20
1 80
-1 80
2 70
-2 70
3 60
-3 60
4 50
-4 50
5 40
-5 40
6 30
-6 30
7 20
-7 20
8 10
-8 10
9 5
-9 5
10 3
-10 3

出力例 4

656

入力例 5

1
0 1

出力例 5

1

Score : 266 pts

Problem Statement

Takahashi manages streetlights installed along a straight road.

The road is represented as a number line, and a streetlight is installed at the origin. There are N signs on the road, where the i-th sign is located at coordinate X_i and has an importance of P_i. Note that multiple signs may exist at the same coordinate.

Takahashi chooses a single non-negative integer R that determines the range illuminated by the streetlight. When R is chosen, the streetlight illuminates the range within distance R from the origin, that is, the range from coordinate -R to coordinate R inclusive. At this time, all signs satisfying |X_i| \leq R are illuminated.

On the other hand, the electrical power cost of the illumination is R^2.

The value obtained by subtracting the power cost R^2 from the total importance of the illuminated signs is called the "effectiveness." That is, the effectiveness when R is chosen is defined as follows:

\left(\sum_{|X_i| \leq R} P_i\right) - R^2

When R = 0 is chosen, the power cost is 0, and only signs at coordinate 0 are illuminated. If there are signs at coordinate 0, the effectiveness equals the sum of their importances (a positive value); otherwise, the effectiveness is 0. Therefore, the maximum effectiveness is always at least 0.

Find the maximum value of the effectiveness when Takahashi optimally chooses a non-negative integer R.

Constraints

  • 1 \leq N \leq 100
  • -100 \leq X_i \leq 100
  • 1 \leq P_i \leq 100
  • X_i and P_i are all integers.

Input

N
X_1 P_1
X_2 P_2
\vdots
X_N P_N
  • The first line contains an integer N representing the number of signs.
  • The i-th of the following N lines contains the coordinate X_i and importance P_i of the i-th sign, separated by a space.

Output

Output the maximum value of the effectiveness in a single line.

Sample Input 1

3
1 10
-2 8
5 3

Sample Output 1

14

Sample Input 2

2
50 1
-50 1

Sample Output 2

0

Sample Input 3

10
0 5
1 10
-1 10
3 20
-3 20
5 15
-5 15
10 50
-10 50
7 30

Sample Output 3

125

Sample Input 4

20
1 80
-1 80
2 70
-2 70
3 60
-3 60
4 50
-4 50
5 40
-5 40
6 30
-6 30
7 20
-7 20
8 10
-8 10
9 5
-9 5
10 3
-10 3

Sample Output 4

656

Sample Input 5

1
0 1

Sample Output 5

1