RETDIG - Return of the Digger

no tags 

The adventures of “Digger” continue as he once again searches for treasure. This time, his money senses detect it underground. His plan is to dig down to it using an automatic pickaxe and his souped-up pneumatic drill.

The treasure is within a thin stretch of land, running West to East, that is made up of dirt and some rocks. This stretch is $L$ ($1 \leq L \leq 200$) metres long. Digger’s money senses are very exact, and he knows the location of the treasure he seeks – it is no more than $10000$ metres below the surface. In addition to money senses, he apparently also has rock senses, which can pinpoint $N$ ($1 \leq N \leq 5000$) rocks among the dirt, none of which will be at a depth of more than $10000$ metres.

Digger’s specially-designed pneumatic drill can only go straight down, and it can tunnel through dirt easily – however, it isn’t equipped with brakes, so it keeps on going until it hits a rock. When this happens, it stops just above the rock, but the drill bit also breaks. This time, Digger doesn’t have to worry about fuel – instead, he just wants to avoid breaking his drill bits! Once stationary, Digger can also use his pickaxe to dig left and right (yes, even through rocks!), but he can’t dig up or down with it.

The treasure is pretty fragile, so Digger definitely doesn’t want to drill right into it. Instead, he can either get to the same depth as it and use his pickaxe to dig to it, or he can use his pneumatic drill to go right past it (either 1 metre to the left or right of it). However, once he gets his hands on the treasure, Digger’s plan isn’t complete – he intends to keep drilling down until he gets to China. As such, he must first navigate past the deepest of the $N$ rocks – at that point, it’s all dirt (or so he hopes...).

Digger can start anywhere on the surface. Determine the minimum amount of drill bits that he must break in order to retrieve the treasure and dig down past all the rocks, if it’s possible at all.

Input

Line $1$: $L$ and $N$ – respectively, the length of the stretch of land (in metres) and the number of rocks.

Lines $2..N+1$: $A$ and $B$ – the $i$th line gives the location of the ($i-1$)th rock, where $A$ is its depth, and $B$ is its distance from the West edge of the stretch of land (both in metres).

Line $N+2$: $Y$ and $X$ – the location of the treasure, where $Y$ is its depth, and $X$ is its distance from the West edge of the stretch of land (both in metres). The treasure will not be within a rock.

Output

If it’s impossible for Digger to reach the treasure and dig down past all the rocks, output “Use dynamite”.

Otherwise, output a single number – the minimum number of drill bits Digger must break to accomplish this.

Example

Input:
10 20
1 5
2 1
2 2
2 4
2 5
2 6
2 8
2 9
3 3
4 7
4 8
4 9
5 3
5 4
5 5
5 6
6 3
10 1
10 2
10 7
8 6
Output:
3
Explanation of Sample:

Digger starts on the surface, 7 metres from the West edge of the stretch of land. He drills down for 3 metres until he hits a rock and breaks his first drill bit. He then uses his pickaxe to walk to the left, and drills down another metre, hitting another rock and breaking his second drill bit. He then walks to the right (through a rock), and drills down for 5 metres, picking up the treasure on the way, until he hits another rock and breaks his third and final drill bit. He then walks to the right and drills down past the last rock. This route is shown below (‘.’: dirt, ‘x’: rock, ‘T’: treasure, ‘D’: drill, ’<’ or ‘>’: pickaxe):

.....x.D..
.xx.xxxDxx
...x..<D..
......D>xx
...xxxxD..
...x...D..
.......D..
......TD..
.......D>.
.xx....xD.
........D.

 


hide comments
linzequn: 2013-05-19 23:04:20

there is something wrong on the map.
No rock is at (2,0);

RE: Oops, thanks - fixed.

Last edit: 2013-05-19 23:04:32

Added by:SourSpinach
Date:2013-05-06
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem