### Woburn Challenge 2018-19 Round 4 - Senior Division

## Problem 2: Farming Simulator

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 ≤ `H` ≤ 500,000,000). He has also prepared `N` (1 ≤ `N` ≤ 3000) holes in the dirt, the `i`-th of which is at a distinct position `P _{i}` (1 ≤

`P`≤

_{i}`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`(1 ≤

_{i}`W`≤ 500,000,000) seconds after the seed has been planted, when Billy is once again at position

_{i}`P`, he may instantly water the seed to make it start growing. Note that the minimum waiting time

_{i}`W`may differ from hole to hole, due to realistically complex details of dirt composition.

_{i}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` ≤ 200.

### Input Format

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`, for

_{i}`i`= 1..

`N`.

### Output Format

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 (4s)
- Stand still for 2 seconds, and water the seed in hole 3 (2s)
- Walk to position 7, and plant a seed in hole 1 (3s)
- Walk to position 8, and plant a seed in hole 2 (1s)
- Walk to position 7, stand still for 1 second, and water the seed in hole 1 (2s)
- Walk to position 8, and water the seed in hole 2 (1s)
- Walk to position 10 (2s)

All Submissions

Best Solutions

**Point Value:** 14 (partial)

**Time Limit:** 3.00s

**Memory Limit:** 64M

**Added:** Mar 22, 2019

**Author:** SourSpinach

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...