Woburn Challenge 2018-19 Round 4 - Senior Division

When Billy needs an extra dose of excitement in his life, he looks no further than to one of his favourite video game series, Farming Simulator. It's filled with wonderful games, though Farming Simulator 16 takes the cake.

Billy's farm in Farming Simulator 16 includes a certain long stretch of dirt, which can be represented as a number line. Billy's currently standing at position ~0~ along the stretch, while his farmhouse is at position ~H~ ~(2 \le H \le 500\,000\,000)~. He has also prepared ~N~ ~(1 \le N \le 3\,000)~ holes in the dirt, the ~i~-th of which is at a distinct position ~P_i~ ~(1 \le P_i \le H-1)~.

Billy can walk along the stretch in either direction at a speed of ~1~ unit per second, and he may also choose to stand still at any point. He'd like to walk around and get a tree growing in each of the ~N~ holes, before ending up at his farmhouse!

Getting a tree growing in the ~i~-th hole is a two-step process. First, at any point in time when Billy is at position ~P_i~, he may instantly plant a seed in the hole. Then, at any point in time at least ~W_i~ ~(1 \le W_i \le 500\,000\,000)~ seconds after the seed has been planted, when Billy is once again at position ~P_i~, he may instantly water the seed to make it start growing. Note that the minimum waiting time ~W_i~ may differ from hole to hole, due to realistically complex details of dirt composition.

Help Billy determine the minimum amount of time required for him to begin at position ~0~, get a tree growing in each of the ~N~ holes, and then end up at position ~H~.

Subtasks

In test cases worth ~14/19~ of the points, ~N \le 200~.

Input Specification

The first line of input consists of two space-separated integers, ~N~ and ~H~.
~N~ lines follow, the ~i~-th of which consists of two space-separated integers, ~P_i~ and ~W_i~, for ~i = 1 \dots N~.

Output Specification

Output a single integer, the minimum number of seconds required for Billy to complete his task.

Sample Input

3 10
7 3
8 1
4 2

Sample Output

15

Sample Explanation

One optimal strategy for Billy is as follows:

• Walk to position ~4~, and plant a seed in hole ~3~ (~4~s)
• Stand still for ~2~ seconds, and water the seed in hole ~3~ (~2~s)
• Walk to position ~7~, and plant a seed in hole ~1~ (~3~s)
• Walk to position ~8~, and plant a seed in hole ~2~ (~1~s)
• Walk to position ~7~, stand still for ~1~ second, and water the seed in hole ~1~ (~2~s)
• Walk to position ~8~, and water the seed in hole ~2~ (~1~s)
• Walk to position ~10~ (~2~s)