题目描述

Cirno 有 $n$ 个整数，分别记作 $a_1,a_2,a_3,...,a_n$。

对于每一个数 $a_i$ 都有一个限制二元组 $(l_i,r_i)$。

Cirno 想知道：

$$\min_{\forall t, a_t \in [l_t,r_t]}\big\{\sum_{i=1}^{n}\sum_{j=1}^{n}\left| a_i - a_j \right|\big\} $$

输入格式

第一行，一个整数 $n$。

以下 $n$ 行，每行一个限制二元组 $(l_i,r_i)$。

输出格式

一行，一个整数，表示答案。

3
1 2
2 3
3 4

4

8
39 42
53 55
51 52
46 47
52 54
33 38
2 7
32 34

910

提示

Sample1说明

$(a_1,a_2,a_3)=(2,3,3)$ 时，答案取到最小值。

数据范围与约定

「本题采用捆绑测试」

• Subtask1( $20\%$ ) : $n \le 10$，且 $r_i - l_i \le 5$
• Subtask2( $20\%$ ) : $n \le 20$
• Subtask3( $20\%$ ) : $n \le 10^3$
• Subtask4( $40\%$ ) : $n \le 10^5$

对于 $100\%$ 的数据 : $n \in (0,10^5]$，$0 \le l_i \le r_i \le 10^9$，答案在 $[0,4 \times 10^{18}]$ 内。