Description

Cirno has $n$ integers, denoted as $a_1,a_2,a_3,...,a_n$.

For each number $a_i$, there is a constraint pair $(l_i,r_i)$.

Cirno wants to know:

$$\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\}$$

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain a constraint pair $(l_i,r_i)$.

Output Format

One line containing an integer, which is the answer.

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

Hint

Sample 1 Explanation

When $(a_1,a_2,a_3)=(2,3,3)$, the answer reaches its minimum.

Constraints and Notes

"This problem uses bundled testdata."

• Subtask 1 ( $20\%$ ): $n \le 10$, and $r_i - l_i \le 5$.
• Subtask 2 ( $20\%$ ): $n \le 20$.
• Subtask 3 ( $20\%$ ): $n \le 10^3$.
• Subtask 4 ( $40\%$ ): $n \le 10^5$.

For $100\%$ of the testdata: $n \in (0,10^5]$, $0 \le l_i \le r_i \le 10^9$, and the answer is within $[0,4 \times 10^{18}]$.

Translated by ChatGPT 5