Donghyuk's Walk

Time limit2sMemory limit512 MB

Summary

With at most 47 blocked cells on an infinite grid, find the largest x coordinate reachable from the origin in exactly K seconds, where waiting is allowed.

Level: Hard8 of 10
Topics: BFS, Graph, Greedy, Math
Solved: No attempts yet

Problem

Donghyuk stands at the origin $(0, 0)$ of an infinite two dimensional grid. Some cells of the grid are blocked, and he cannot enter a blocked cell. The origin is not blocked.

Each second Donghyuk may move to one of the four cells next to his current cell (up, right, down, left) that is not blocked. He may also stay where he is.

Given the blocked cells and the time $K$ , write a program that finds the largest $x$ coordinate of a cell where Donghyuk can be after $K$ seconds.

Input

The first line contains the number of blocked cells $N$ and the time $K$ ( $0 \le N \le 47$ , $1 \le K \le 10^9$ ).

Each of the next $N$ lines contains the $x$ coordinate and the $y$ coordinate of one blocked cell. Both coordinates are integers whose absolute value is at most $10^9$ .

All blocked cells are distinct, and the origin is not among them.

Output

Print the largest $x$ coordinate of a cell where Donghyuk can be after $K$ seconds.

Examples4

Example 1
Input
```
4 4
1 -2
1 -1
1 0
1 1
```
Expected output
```
2
```
Example 2
Input
```
4 9
-1 0
0 -1
0 1
1 0
```
Expected output
```
0
```
Example 3
Input
```
0 1000
```
Expected output
```
1000
```

Example 4

Input

11 47
1 0
0 -1
0 1
-1 -2
-1 2
-2 -3
-2 3
-3 -4
-3 4
-4 -5
-4 5

Expected output