题目背景

我把恶意作为我的筹码

我用仇恨见证我的挣扎

赖以维生的不可能放下

那就一路到底 撞上南墙留下浑身伤疤

——MOCKER44. / 星尘《血路》

题目描述

小 S 和小 W 在整理区间。

有 $n$ 个开区间 $(l_i,r_i)$，保证至少存在一个公共整点，即存在整数 $x$ 满足 $\forall i\in[1,n],l_i\lt x\lt r_i$。

为了让区间变得美观，小 S 不希望区间有交。形式化地，不存在区间 $i,j\in[1,n],i\ne j$ 使得存在实数 $x$ 满足 $l_i\lt x\lt r_i$ 且 $l_j\lt x\lt r_j$。

为实现小 S 的目标，小 W 每次可任选一个区间 $(l_i,r_i)$，将其平移一个单位长度，即变为 $(l_i-1,r_i-1)$ 或 $(l_i+1,r_i+1)$，值域不限。

时间紧迫，请你求出实现目标的最小操作次数。

输入格式

第一行一个整数 $n$，表示区间数量。

接下来 $n$ 行，每行两个整数 $l_i,r_i$，表示一个区间的左右端点。

输出格式

一行一个整数，表示最小操作次数。

输入 #1

4
1 4
2 4
2 4
2 4

输出 #1

8

输入 #2

17
686370889 1720353024
659689023 1973942221
534239841 1586709731
904474839 1893594873
152782165 1512421517
116676779 1900192139
248001261 1727466002
1122615537 2083079192
823751791 1926709565
902687686 1759405986
1040603071 1319691596
586374009 1636748002
1138407926 1367736779
1001499057 1311162627
250559231 1566376279
401875955 1260568829
42703863 2059989422

输出 #2

55507923453

输入 #3

18
1 1509841542
565464298 1748265476
225187646 1113339917
380156253 957131519
68203883 1701383555
561555666 984822029
588027619 1037555161
383772731 1009364098
175015314 1742510831
739196183 1094919079
540885320 866640854
395164831 1532916512
146487448 1109032833
717561548 1323200759
59582458 1199018161
76352958 1065234771
91132065 1066182313
452152775 1187676152

输出 #3

52095432993

说明/提示

样例 $1$ 解释：一种最优解为 $(-1,2),(2,4),(4,6),(6,8)$，操作次数为 $2+0+2+4=8$。

对于所有数据，$1\le n\le 5000,0\le l_i\lt r_i\lt 2^{31}$，保证 $n$ 与测试点编号奇偶性相同。

\begin{array}{|c|c|} \hline \textbf{测试点} & \textbf{特殊性质}\\ \hline 1,2& n\le 5,r_i\le 6\\ \hline 3,4 & n\le 9\\ \hline 5,6 & n\le 18\\ \hline 7,8 & n\le 100\\ \hline 9,10,11,12,13,14 & n\le 500\\ \hline 15,16,17,18,19,20 & \textbf{无}\\ \hline \end{array}