[Cnoi2020] 领域极限

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}]$ 内。