题目描述

给定一个由 $n$ 个二元组构成的序列 $A=\{(a_i, b_i)\}$。

设 $w(i, j) = b_i - b_j$，定义 $c_i$ 的值如下：

$$c_i=\sum_{1\le j<i}[a_j\le a_i]w(i, j) + [a_j>a_i]w(i, j)^2+\sum_{i<j\le n} [a_j\le a_i]w(i, j)^2+[a_j>a_i]w(i, j)$$

你可以对 $A$ 进行一次重排，请你求出重排后 $\sum\limits_{1\le i\le n} c_i$ 的最小值。

注意，$[P]$ 为艾弗森括号，其定义为：

$$[P] = \left\{\begin{matrix} 1 & \text{P 为真}\\ 0 & \text{P 为假} \end{matrix}\right.$$

例如：$[1\ge0] = 1, [2 < 1] = 0$。

保证答案不超过 long long 数据类型的储存范围，即小于 $2^{63}$。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行两个整数，分别表示 $a_i$ 和 $b_i$。

输出格式

输出共一行一个整数，表示答案。

3
12 2
4 2
6 2

0

5
4 2
2 6
3 4
2 5
4 7

20

数据规模与约定

对于 $10\%$ 的数据，有 $n\le10$；

对于 $30\%$ 的数据，有 $n\le2\times10^3$；

对于上述以外 $30\%$ 的数据，保证 $a_i = b_i$；

对于 $100\%$ 的数据，有 $3\le n\le10^6$，$1\le a_i, b_i\le 10^6$。

下发样例

附件