AT_abc395_f [ABC395F] Smooth Occlusion

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.

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 $

Print the answer.

### Sample Explanation 1 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 Explanation 2 It is possible that the teeth already fit together well without any changes. ### Sample Explanation 3 Note that the answer may exceed the $ 32 $ -bit integer range. ### 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.