F - Smooth Occlusion Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

高橋くんには歯が 2N 本あり、N 本は上の歯、残りの N 本は下の歯です。

左から i 本目 (1\leq i\leq N) の上の歯の長さは U _ i で、左から i 本目 (1\leq i\leq N) の下の歯の長さは D _ i です。

高橋くんの歯が次の 2 つの条件をどちらも満たしているとき、歯が「うまく噛み合っている」ということにします。

  • ある整数 H が存在し、1\leq i\leq N を満たすすべての整数 i について、U _ i+D _ i=H が成り立つ。
  • 1\leq i\lt N を満たすすべての整数 i について、\vert U _ i-U _ {i+1}\vert\leq X が成り立つ。

高橋くんは次の操作を好きなだけ繰り返すことができます。

  • 1 円を支払って歯削り機を使い、長さが正であるような歯を 1 つ選んでその歯の長さを 1 減らす。

この操作以外の方法で歯の長さを変えることはできません。

高橋くんが歯をうまく噛み合わせるために支払うことになる最小の金額を求めてください。

制約

  • 2\leq N\leq2\times10 ^ 5
  • 1\leq U _ i\leq10 ^ 9\ (1\leq i\leq N)
  • 1\leq D _ i\leq10 ^ 9\ (1\leq i\leq N)
  • 1\leq X\leq10 ^ 9
  • 入力はすべて整数

入力

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

N X
U _ 1 D _ 1
U _ 2 D _ 2
\vdots
U _ N D _ N

出力

答えを出力せよ。

入力例 1

4 3
3 1
4 1
5 9
2 6

出力例 1

15

はじめ、高橋くんのそれぞれの歯の高さは以下のようになっています。

たとえば、以下のようにして高橋くんの歯をうまく噛み合わせることができます。

15 円を支払うことでそれぞれの歯をこの長さにすることができます。

14 円以下を支払って高橋くんの歯をうまく噛み合わせることはできないため、15 を出力してください。

入力例 2

4 1000000000
3 3
3 3
3 3
3 3

出力例 2

0

歯の長さを変えなくてもうまく噛み合っている場合があります。

入力例 3

4 1
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1 1

出力例 3

5999999994

答えが 32\operatorname{bit} 整数に収まらない場合があることに注意してください。

入力例 4

15 128
748 169
586 329
972 529
432 519
408 587
138 249
656 114
632 299
984 755
404 772
155 506
832 854
353 465
387 374
567 385

出力例 4

9460

Score : 500 points

Problem Statement

Takahashi has 2N teeth: N upper teeth and N lower teeth.

The length of the i-th upper tooth from the left (1 \leq i \leq N) is U _ i, and the length of the i-th lower tooth from the left (1 \leq i \leq N) is D _ i.

His teeth are said to “fit together well” if both of the following conditions are satisfied:

  • There exists an integer H such that U _ i + D _ i = H for every integer i with 1 \leq i \leq N.
  • \lvert U _ i - U _ {i+1} \rvert \leq X for every integer i with 1 \leq i < N.

He can perform the following operation any number of times:

  • Pay 1 yen to use a tooth-grinding machine, choose exactly one tooth whose length is positive, and reduce its length by 1.

No other method may be used to change the lengths of the teeth.

Find the minimum total amount of money he needs to pay to make his teeth fit together well.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq U _ i \leq 10^9 \ (1 \leq i \leq N)
  • 1 \leq D _ i \leq 10^9 \ (1 \leq i \leq N)
  • 1 \leq X \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N X
U _ 1 D _ 1
U _ 2 D _ 2
\vdots
U _ N D _ N

Output

Print the answer.

Sample Input 1

4 3
3 1
4 1
5 9
2 6

Sample Output 1

15

Initially, Takahashi’s teeth have the following lengths:

For example, you can make them fit together well in the following way:

It costs 15 yen to achieve these lengths.

It is impossible to make them fit together well with 14 yen or less, so print 15.

Sample Input 2

4 1000000000
3 3
3 3
3 3
3 3

Sample Output 2

0

It is possible that the teeth already fit together well without any changes.

Sample Input 3

4 1
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1 1

Sample Output 3

5999999994

Note that the answer may exceed the 32-bit integer range.

Sample Input 4

15 128
748 169
586 329
972 529
432 519
408 587
138 249
656 114
632 299
984 755
404 772
155 506
832 854
353 465
387 374
567 385

Sample Output 4

9460