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 Pi (1 ≤ Pi ≤ 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 Pi, he may instantly plant a seed in the hole. Then, at any point in time at least Wi (1 ≤ Wi ≤ 500,000,000) seconds after the seed has been planted, when Billy is once again at position Pi, he may instantly water the seed to make it start growing. Note that the minimum waiting time Wi 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 ≤ 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, Pi and Wi, for 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...