D - 気温の統一 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君はビル管理会社で働いています。管理しているビルには N 個の部屋があり、部屋 i（1 \leq i \leq N）の広さは S_i、現在の室温は P_i ℃です。

高橋君は全部屋の室温を同じ整数値 T ℃に統一したいと考えています。部屋 i の室温を 1 ℃上昇または下降させるのに必要なコストはいずれも S_i です。すなわち、部屋 i の室温を P_i ℃から T ℃に変更するのに必要なコストは S_i \times |P_i - T| です。

高橋君は目標温度 T を任意の整数から自由に選ぶことができます。すべての部屋の室温を T ℃に統一するための総コスト

\sum_{i=1}^{N} S_i \times |P_i - T|

の最小値を求めてください。

制約

  • 1 \leq N \leq 150000
  • 1 \leq S_i \leq 10^4
  • -10^9 \leq P_i \leq 10^9
  • 入力はすべて整数である。

入力

N
S_1 P_1
S_2 P_2
\vdots
S_N P_N
  • 1 行目には、部屋の数を表す整数 N が与えられる。
  • 続く N 行のうち i 行目には、部屋 i の広さ S_i と現在の室温 P_i がスペース区切りで与えられる。

出力

すべての部屋の室温を同一の整数値に統一するための総コストの最小値を整数として 1 行で出力せよ。

入力例 1

3
2 18
1 23
2 20

出力例 1

7

入力例 2

2
5 0
5 10

出力例 2

50

入力例 3

8
3 -5
2 0
6 4
1 -2
5 10
4 4
2 7
3 -5

出力例 3

104

入力例 4

15
8 12
5 -3
7 7
4 7
10 20
6 -10
3 0
9 15
2 -3
1 100
8 12
5 30
7 -20
4 15
6 7

出力例 4

879

入力例 5

1
10000 -1000000000

出力例 5

0

Score : 400 pts

Problem Statement

Takahashi works at a building management company. The building he manages has N rooms, where room i (1 \leq i \leq N) has a size of S_i and a current temperature of P_i ℃.

Takahashi wants to unify the temperature of all rooms to the same integer value T ℃. The cost to raise or lower the temperature of room i by 1 ℃ is S_i in either case. That is, the cost to change the temperature of room i from P_i ℃ to T ℃ is S_i \times |P_i - T|.

Takahashi is free to choose the target temperature T as any integer. Find the minimum value of the total cost to unify the temperature of all rooms to T ℃:

\sum_{i=1}^{N} S_i \times |P_i - T|

Constraints

  • 1 \leq N \leq 150000
  • 1 \leq S_i \leq 10^4
  • -10^9 \leq P_i \leq 10^9
  • All input values are integers.

Input

N
S_1 P_1
S_2 P_2
\vdots
S_N P_N
  • The first line contains an integer N representing the number of rooms.
  • The i-th of the following N lines contains the size S_i and the current temperature P_i of room i, separated by a space.

Output

Output in a single line the minimum total cost to unify the temperature of all rooms to the same integer value, as an integer.

Sample Input 1

3
2 18
1 23
2 20

Sample Output 1

7

Sample Input 2

2
5 0
5 10

Sample Output 2

50

Sample Input 3

8
3 -5
2 0
6 4
1 -2
5 10
4 4
2 7
3 -5

Sample Output 3

104

Sample Input 4

15
8 12
5 -3
7 7
4 7
10 20
6 -10
3 0
9 15
2 -3
1 100
8 12
5 30
7 -20
4 15
6 7

Sample Output 4

879

Sample Input 5

1
10000 -1000000000

Sample Output 5

0