← 返回题目列表

AtCoder · awc0105_d

D. 温度均匀

中文机器翻译题面 查看原题

分数: 400 分

问题陈述

高桥在一家建筑管理公司工作。他管理的大楼有 N 房间,房间在哪里 i (1 \leq i \leq N)的大小为 S_i 和当前温度 P_i ℃.

高桥想要将所有房间的温度统一为相同的整数值 T ℃。升高或降低房间温度的成本 i by 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
  • 第一行包含一个整数 N 代表房间数量。
  • 的 i- 以下各项 N 行包含大小 S_i 和当前温度 房间的 P_i 房间的 i,用空格分隔。

输出

在单行中输出将所有房间的温度统一为相同整数值的最小总成本(作为整数)。


示例输入 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