[USACO04OPEN] MooFest G

题目背景

[P5094 [USACO04OPEN] MooFest G 加强版](https://www.luogu.com.cn/problem/P5094)

题目描述

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

输入输出格式

输入格式


第一行:单个整数 $n$,$1\le n\le2\times 10^4$ 第二行到第 $n + 1$ 行:第 $i + 1$ 行有两个整数 $v_i$ 和 $x_i$($1\le v_i,x_i\le2\times 10^4$)。

输出格式


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

输入输出样例

输入样例 #1

4
3 1
2 5
2 6
4 3

输出样例 #1

57