题目描述

位于一条笔直的公路的一边上有 $n$ 条村庄用一条数轴来描述这条公路，每个村庄都有一个整数坐标 $x$ 和该村庄的人数 $p$。两个村庄的距离定义为他们坐标差的绝对值。现在需要在某个村庄里修建一个邮局，那么这个邮局应修建在那个村庄才能使得各村庄到邮局的距离总和最小。

输入格式

第一行是一个整数 $n$，表示村庄数量。

接下来的 $n$ 行，每行包含两个整数 $x_i$，$p_i$，表示第 $i$ 个村庄的坐标和该村庄的人数。

数据范围

$1 \lt n \le 30000$

$0 \lt x_i \le 100000$

$0 \lt p_i \le 100$

输出格式

所有人到邮局的距离总和的最小值。

样例

5
7 6
1 3
10 5
6 2
3 7

62