分数: 1000 点
问题陈述
AtCoDeer 发现鹿 N 躺在桌子上的矩形,每个都有高度 1。 如果我们将桌子的表面视为一个二维平面, i第一个矩形 i(1≤i≤N) 涵盖的垂直范围 [i-1,i] 和水平范围 [l_i,r_i],如下图所示:

AtCoDeer 将水平移动这些矩形,以便所有矩形都连接起来。 对于每个矩形,将其水平移动距离的成本为 x是 x。 找出实现连接的最低成本。 可以证明,在问题的约束下,这个值始终是整数。
约束
- 所有输入值均为整数。
- 1≤N≤10^5
- 1≤l_i<r_i≤10^9
部分分数
- 300 通过满足以下条件的测试集将获得积分 1≤N≤400 和 1≤l_i<r_i≤400.
输入
输入由标准输入按以下格式给出:
N l_1 r_1 l_2 r_2 : l_N r_N
输出
打印实现连接的最低成本。
示例输入 1
3 1 3 5 7 1 3
示例输出 1
2
第二个矩形应向左移动距离 2.
示例输入 2
3 2 5 4 6 1 4
示例输出 2
0
矩形已经连接,因此不需要移动。
示例输入 3
5 999999999 1000000000 1 2 314 315 500000 500001 999999999 1000000000
示例输出 3
1999999680
示例输入 4
5 123456 789012 123 456 12 345678901 123456 789012 1 23
示例输出 4
246433
示例输入 5
1 1 400
示例输出 5
0