WC '18 Contest 4 S2 - Farming Simulator

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.4s
Memory limit: 64M

Author:
Problem type
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 \leq 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 \ldots 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 (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)

Comments

There are no comments at the moment.