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 along the stretch, while his farmhouse is at
position
. He has also prepared
holes in the dirt, the
-th of which is at a
distinct position
.
Billy can walk along the stretch in either direction at a speed of
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
holes, before ending up at his farmhouse!
Getting a tree growing in the -th hole is a two-step process. First,
at any point in time when Billy is at position
, he may instantly
plant a seed in the hole. Then, at any point in time at least
seconds after the seed has been planted,
when Billy is once again at position
, he may instantly water the
seed to make it start growing. Note that the minimum waiting time
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 , get a tree growing in each of the
holes, and
then end up at position
.
Subtasks
In test cases worth of the points,
.
Input Specification
The first line of input consists of two space-separated integers,
and
.
lines follow, the
-th of which consists of two space-separated
integers,
and
, for
.
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
, and plant a seed in hole
(
s)
- Stand still for
seconds, and water the seed in hole
(
s)
- Walk to position
, and plant a seed in hole
(
s)
- Walk to position
, and plant a seed in hole
(
s)
- Walk to position
, stand still for
second, and water the seed in hole
(
s)
- Walk to position
, and water the seed in hole
(
s)
- Walk to position
(
s)
Comments