题目描述

每一年，约翰的 $N$ 只奶牛参加奶牛狂欢节。这是一个全世界奶牛都参加的大联欢。狂欢节包括很多有趣的活动，比如干草堆叠大赛、跳牛栏大赛，奶牛之间有时还相互扎屁股取乐。当然，她们会排成一列嚎叫，来欢庆她们的节日。奶牛们的叫声实在刺耳，以致于每只奶牛的听力都受到不同程度的损伤。现在告诉你奶牛 $i$ 的听力为 $v_i$ ，这表示如果奶牛 $j$ 想说点什么让她听到，必须用高于 $v_i \times dis(i,j)$ 的音量。因此，如果奶牛 $i$ 和 $j$ 想相互交谈，她们的音量必须不小于 $\max (v_i,v_j) \times dis(i,j)$。其中 $dis(i,j)$ 表示她们间的距离。

现在 $N$ 只奶牛都站在一条直线上了，每只奶牛还有一个坐标 $x_i$。如果每对奶牛都在交谈，并且使用最小音量，那所有 $N(N-1)/2$ 对奶牛间谈话的音量之和为多少？

输入格式

第 $1$ 行输入一个整数 $N$ 。

接下来 $N$ 行，每行输入两个数 $v_i$ 和 $x_i$ ，分别代表第 $i$ 头奶牛的听力和坐标。

输出格式

输出一个数，代表这 $N(N-1)/2$ 对奶牛谈话时的音量之和。

4
3 1
2 5
2 6
4 3

57

提示

数据范围

因为原数据下 $O(N^2)$ 算法可以通过，所以新添加了一些增强数据。

原数据作为子任务 $1$，新添加的数据作为子任务 $2$。

• 子任务 $1$（$1$ 分）：$1 \leq N,V_i,x_i \leq 2 \times 10^4$。
• 子任务 $2$（$99$ 分）：$1 \leq N,V_i,x_i \leq 5 \times 10^4$。