题目描述

在数轴上有 $n$ 个点，第 $i$ 个点的坐标为 $x_i$，该点上有 $c_i$ 个人。

请从这些点中，挑出两个点作为聚集点，其余点上的人都要向这两个点靠拢（选一个更近的即可），请求出这些人移动距离之和的最小值。

输入格式

• 第一行：单个整数 $n$
• 第二行到第 $n+1$ 行：第 $i+1$ 行有两个整数表示 $x_i$ 与 $c_i$。
• 保证 $x_1< x_2< \dots < x_n$

输出格式

• 单个整数：表示答案

6
1 10
2 100
3 10
4 10
5 100
6 10

40

样例解释 1

选2与5

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 100$
• 对于 $60\%$ 的数据，$1\leq n\leq 20000$
• 对于 $100\%$ 的数据，$1\leq n\leq 300000$
• $-10^7 \leq x_i\leq 10^7$
• $0 \leq c_i\leq 10^8$