奶牛集会

题目背景

MooFest, 2004 Open

题目描述

约翰的N 头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多,比如堆干草,跨栅栏,摸牛仔的屁股等等。它们参加活动时会聚在一起,第i 头奶牛的坐标为Xi,没有两头奶牛的坐标是相同的。奶牛们的叫声很大,第i 头和第j 头奶牛交流,会发出max{Vi; Vj}×|Xi − Xj | 的音量,其中Vi 和Vj 分别是第i 头和第j 头奶牛的听力。 假设每对奶牛之间同时都在说话,请计算所有奶牛产生的音量之和是多少。

输入输出格式

输入格式


• 第一行:单个整数N,1 ≤ N ≤ 20000 • 第二行到第N + 1 行:第i + 1 行有两个整数Vi 和Xi,1 ≤ Vi ≤ 20000; 1 ≤ Xi ≤ 20000

输出格式


• 单个整数:表示所有奶牛产生的音量之和

输入输出样例

输入样例 #1

4
3 1
2 5
2 6
4 3

输出样例 #1

57

说明

朴素O(N2) 类似于归并排序的二分O(N logN) 树状数组O(N logN)