匹配

题目描述

有 $n$ 位选手参加光头杯，保证 $n$ 是偶数。你要安排 $n/2$ 场比赛，每场比赛中挑选 $2$ 位选手同台竞技。

需要保证每位选手恰好参加 $1$ 场比赛。

比赛双方都会有得分。第 $i$ 位选手的得分总是在区间 $[l_i,r_i]$ 中，而具体得几分与对手无关，也无法预测。

因此，如果安排第 $i$ 位选手与第 $j$ 位选手同台竞技，能得到的节目效果为：

$\max_{l_i \leq x \leq r_i}{\max_{l_j \leq y \leq r_j} |x-y|}$

求所有匹配方案中，节目效果总和的最大值。

输入格式

第一行一个正偶数 $n$。

接下来 $n$ 行，其中第 $i$ 行输入 $l_i$ 和 $r_i$ 。

请使用较快的输入方式。

输出格式

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

样例输入1

4
0 10
7 7
4 9
2 15

样例输出1

18

样例输入2

8
328956838 395856535
332499430 962948538
117688285 221960544
80767842 975125829
207845649 622670457
265742296 913618029
66376350 724078542
123909914 141972369

样例输出2

2837431466

数据范围

对于 $30%$ 的数据， $n \leq 8$ 。

对于 $50%$ 的数据， $n \leq 16$ 。

对于另外 $20%$ 的数据， $l_i = r_i$

对于另外 $10%$ 的数据， $r_i - l_i$ 为常数。

对于 $100%$ 的数据，$2 \leq n \leq 10^6 , 0 \leq l_i \leq r_i \leq 10^9$