[IOI2016] railroad

Anna 在一个游乐园工作。她负责建造一个新的过山车铁路。她已经设计了影响过山车速度的 $n$ 个特殊的路段（方便起见标记为 $0$ 到 $n-1$）。现在 Anna 必须要把这些特殊的路段放在一起并提出一个过山车的最后设计。为了简化问题，你可以假设过山车的长度为零。 对于 $0$ 和 $n-1$ 之间的每个 $i$，这个特殊的路段 $i$ 具有如下两个性质： - 当进入这个路段时，有一个速度限制：过山车的速度必须小于或等于 $s_i$ $\text{km/h}$（每小时千米）。 - 当离开这个路段时，过山车的速度刚好是 $t_i$ $\text{km/h}$，不管过山车进入该路段时的速度如何。 最后完成的过山车设计是一个以某种顺序包含这 $n$ 个特殊路段的单一铁路线。这 $n$ 个路段中的每一个应当被使用刚好一次。连续的路段之前用铁轨来连接。Anna 应该选择这 $n$ 个路段的顺序，然后确定每段铁轨的长度。铁轨的长度以米来衡量，可以是任意的非负整数（可以为零）。 两个特殊路段之间的每 $1$ 米铁轨可以将过山车的速度减慢 $1$ $\text{km/h}$。在这个过山车铁路的起点，过山车按照 Anna 选择的顺序进入第一个特殊路段时的速度是 $1$ $\text{km/h}$。 最后的设计还必须满足以下要求： - 过山车在进入这些特殊路段时不能违反任一个速度限制。 - 过山车的速度在任意时刻为正。 你的任务是找出这些路段之间铁轨的最小可能总长度（这些路段之间铁轨总长度的最小值）。如果 $m=0$ 你只需要检查是否存在一个有效的过山车设计，使得每段铁轨的长度为零。 **举例** ``` 4 1 1 7 4 3 5 8 6 6 ``` 在这个样例中有 $4$ 个特殊的路段。最好的解是按照 $0,3,1,2$ 的顺序构造，连接这些路段的铁轨长度分别是 $1,2,0$。下面给出过山车沿铁路铁轨的行驶方式： - 最初过山车的速度是 $1$ km/h。 - 过山车由进入 $0$ 号路段开始行进。 - 过山车以 $7$ $\text{km/h}$ 的速度离开 00 号路段。 - 然后有一段长度为 $1$ $\text{m}$ 的铁轨。过山车在到达这段铁轨的末端时速度为 $6$ $\text{km/h}$。 - 过山车以 $6$ $\text{km/h}$ 的速度进入 $3$ 号路段并以相同的速度离开该路段。 - 在离开 $3$ 号路段后，过山车走过一段 $2$ $\text{m}$ 长的铁轨。速度降至 $4$ $\text{km/h}$。 - 过山车以 $4$ $\text{km/h}$ 的速度进入 $1$ 号路段，并且以 $3$ $\text{km/h}$ 的速度离开该路段。 - 离开 $1$ 号路段后，过山车立即进入 $2$ 号路段。 - 过山车离开 $2$ 号路段。其最终速度是 $8$ $\text{km/h}$。 路段之间的铁轨总长度：$1+2+0=3$。

- 第一行：两个整数 $n$ 和 $m$，其中 $m=0$ 表示当答案不为 $0$ 时，你可以返回任意正整数，$m=1$ 表示你需要返回正确答案。 - 接下来 $n$ 行：第 $i$ 行的两个整数表示 $s_{i-1}$ 和 $t_{i-1}$。

共一行，所有铁轨的最小可能总长度。（当 $m=0$ 时，如果存在一个有效的过山车设计使得每段铁轨的长度均为零，则函数返回零，如果上述设计不存在，则输出任意的正整数）。

4 1
1 7
4 3
5 8
6 6

3

对于 $100\%$ 的数据，$1 \le n \le 2 \times {10}^5$，$ 1 \le s_i \le 10^9$，$1 \le t_i \le 10^9$。