题目描述

鹿のAtCoDeer君发现桌子上放着 $N$ 个纵向长度为 $1$ 的细长矩形。若将桌面视为一个二维平面，如下图所示，第 $i$（$1 \leq i \leq N$）个矩形的纵向范围为 $[i-1, i]$，横向范围为 $[l_i, r_i]$。

AtCoDeer君想要通过将这些矩形分别在水平方向上移动，使得所有矩形都连在一起。每个矩形在水平方向上移动距离 $x$ 需要支付 $x$ 的代价。请计算使所有矩形连成一块所需的最小总代价。在本题的约束条件下，可以证明该值为整数。

输入格式

输入经标准输入给出，格式如下：

$N$
$l_1$ $r_1$
$l_2$ $r_2$
$\cdots$
$l_N$ $r_N$

输出格式

输出使所有矩形连成一块所需的最小总代价。

输入输出样例 #1

输入 #1

3
1 3
5 7
1 3

输出 #1

2

输入输出样例 #2

输入 #2

3
2 5
4 6
1 4

输出 #2

0

输入输出样例 #3

输入 #3

5
999999999 1000000000
1 2
314 315
500000 500001
999999999 1000000000

输出 #3

1999999680

输入输出样例 #4

输入 #4

5
123456 789012
123 456
12 345678901
123456 789012
1 23

输出 #4

246433

输入输出样例 #5

输入 #5

1
1 400

输出 #5

0

说明/提示

数据范围

• 所有输入均为整数。
• $1 \leq N \leq 10^5$
• $1 \leq l_i < r_i \leq 10^9$

部分分

• 若对满足 $1 \leq N \leq 400$ 以及 $1 \leq l_i < r_i \leq 400$ 的数据集输出正确，可获得 $300$ 部分分。

样例解释 1

将第 $2$ 个矩形向左移动 $2$ 达到最优。

样例解释 2

本来已经连成一块，无需移动。

由 ChatGPT 5 翻译