一艘新的海盗帆船正在建造中。这艘船有 $N$ 根桅杆，每根桅杆被分为若干个单位长度的节——桅杆的高度等于其节数。每根桅杆上装有若干张帆，每张帆正好占据一个节。同一根桅杆上的帆可以任意分布在不同的节上，但每个节最多只能装一张帆。

当暴露在风中时，不同的帆配置会产生不同大小的推力。位于其他帆前方且处于同一高度的帆受到的风力较小，产生的推力也较小。对于每一张帆，我们定义其“低效值”为在该帆后方且处于同一高度的帆的总数。注意，“前方”和“后方”与船的朝向有关：在下图中，“前方”指左侧，“后方”指右侧。

一种配置的总低效值为所有单张帆的低效值之和。

这艘船有 6 根桅杆，从前方（图像左侧）到后方的高度分别为 3, 5, 4, 2, 4 和 3。这种帆的分布方式产生的总低效值为 10。每张帆的个体低效值写在帆的内部。

题目描述

编写一个程序，给定 $N$ 根桅杆中每一根的高度和帆的数量，确定最小可能的总低效值。

输入格式

第一行包含一个整数 $N$ ($2 \le N \le 100\,000$)，表示船上的桅杆数量。 接下来的 $N$ 行，每行包含两个整数 $H$ 和 $K$ ($1 \le H \le 100\,000, 1 \le K \le H$)，分别表示对应桅杆的高度和帆的数量。桅杆按从船头到船尾的顺序给出。

输出格式

输出一个整数，即最小可能的总低效值。

说明：请使用 64 位整数类型来计算并输出结果（C/C++ 中的 long long，Pascal 中的 int64）。

子任务

在总分 25 分的测试用例中，帆的排列方式总数最多为 $1\,000\,000$。

样例

输入 1

6
3 2
5 3
4 1
2 1
4 3
3 2

输出 1

10

说明 1

该样例对应于前一页的图示。