题目描述

シカのAtCoDeerくんは縦の長さが $1$ の細長い長方形が $N$ 個机に置いてあるのを見つけました。 机を二次元平面とみなすと、以下の図のように、$i(1≦i≦N)$ 個目の長方形は、縦は $[i-1,i]$ の範囲を、横は $[l_i,r_i]$ の範囲を占めています。

AtCoDeerくんはこの長方形をそれぞれ横に動かすことで、全ての長方形を連結にしようと考えました。 各長方形は横に距離 $x$ 動かすのに $x$ のコストがかかります。 全ての長方形を連結にするのに必要なコストの最小値を求めてください。 問題の制約のもとでこの値は整数になることが証明できます。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $l_1$ $r_1$ $l_2$ $r_2$ : $l_N$ $r_N$

输出格式

必要なコストの最小値を出力せよ。

题目大意

题目描述

AtCoDeer君看到桌上放着 $N$ 个细长的长方形。把桌面看作平面，则如下图所示：第 $i(1 \leq i \leq N)$ 个长方形占了纵 $[i-1,i]$ ，横 $[l_i,r_i]$ 的空间。

AtCoDeer可以移动每个长方形，来使所有长方形连接起来。每个长方形横向移动 $x$ 的距离其代价为 $x$ 。请求出将所有长方形连接所需的最小代价。可以证明答案一定为整数。

数据范围

• 对于 $30\%$ 的数据：
• $1 \leq N \leq 400$
• $1 \leq l_i < r_i \leq 400$
• 对于 $100\%$ 的数据：
• 输入全为整数。
• $1 \leq N \leq 10^5$
• $1 \leq l_i < r_i \leq 10^9$

输入

输入按以下形式：

$$N$$ $$l_1 r_1$$ $$l_2 r_2$$ $$:$$ $$l_N r_N$$

输出

输出必要代价的最小值。

样例

样例见原题面； 样例 2,5 的输出都为 $0$ 。

样例解释

样例1解释

将第 $2$ 个长方形向左移动 $2$ 单位长度时代价最小。

样例2解释

开始时长方形间就是连接的，所有没必要进行移动。

感谢@ミク 提供的翻译

3
1 3
5 7
1 3

2

3
2 5
4 6
1 4

0

5
999999999 1000000000
1 2
314 315
500000 500001
999999999 1000000000

1999999680

5
123456 789012
123 456
12 345678901
123456 789012
1 23

246433

1
1 400

0

提示

制約

• 入力は全て整数である。
• $1≦N≦10^5$
• $1≦l_i\ <\ r_i≦10^9$

部分点

• $1≦N≦400$, $1≦l_i\ <\ r_i≦400$ を満たすデータセットに正解した場合は、部分点として $300$ 点が与えられる。

Sample Explanation 1

$2$ 個目の長方形を左に $2$ 動かすのが最小です。

Sample Explanation 2

はじめから連結になっているため、動かす必要はありません。