Problem B
Easter Eggs

Photo by darknesschildsin

Easter is here again, and as usual, the Easter Bunny has more things on his mind than a gnu balancing a dish of exotic fruits on its head. As you know, one of the Easter Bunny’s tasks is to bring easter eggs containing a nourishing assortment of carrots and sweets to all the good folks who still believe in him. The eggs have to be delivered before dawn, and it is already midnight, so the Easter Bunny is starting to feel the kind of stressed-out panic that only a little rabbit can feel. It has become blatantly clear to the Easter Bunny that he will not be able to deliver all the eggs, and hence, he has asked you to help him minimise the damage by writing a program that helps him deliver as many eggs as possible.

The Easter Bunny has a (sufficiently large) store of eggs in his secret underground hideout, and he wants to carry one egg to everyone in the world who believes in him. The world, as you probably know, is flat, and hence we model a location in the world as a point in a two-dimensional plane. The eggs need to be delivered strictly before sunrise, as the Easter Bunny mustn’t be seen. What complicates matters is that the sun rises at different times depending on where you are in the world. At coordinate $(x, y)$, the sun rises $720 + x/2000$ minutes after midnight.

When travelling between two points in the world, the Easter Bunny always travels along the straight line between them. Being a furry little bunny rabbit (rather than, say, a kangaroo), the Easter Bunny’s egg carrying capacity is very limited, and the more eggs he carries, the harder time he has keeping his pace up. When not carrying any eggs, the Easter Bunny can move (jump) at a speed of $v$ metres per second, but each extra egg he carries makes it twice as hard to keep a decent speed. Hence, when carrying $i$ eggs, he is able to cover $v\cdot 2^{-i}$ metres per second.

Since we are already running on a tight schedule, we don’t bother modelling the finer nuances of the Easter Bunny’s egg delivering. Hence, we assume that everything but moving from one point to another takes zero time (when, in practice, the Easter Bunny usually needs a moment or two to e.g. find a good hiding place for an egg).

Input

The input consists of several test cases, at most $5$. The first line of a test case contains two integers $1 \le n \le 17$, $1 \le v \le 100$, where $n$ is the number of eggs to be delivered and $v$ is the speed of the bunny while not carrying anything. Then follow $n$ lines, each containing two integers $x$ and $y$, indicating where to deliver the $n$ eggs. The Easter Bunny’s secret hideout is located at $x = 0$, $y = 0$.¹ The length unit of the coordinates is metres, and you may assume that all coordinates have absolute value bounded by $10^6$.

There is a blank line between any two consecutive test cases. Input is terminated by a case where $n = 0$ and $v = 0$, which should not be processed.

Output

For each test case, output a line containing the maximal number of eggs that the Easter Bunny will be able to place before dawn.

4 5
-42000 0
0 42000
42000 0
0 -42000

8 1
50 8
-4711 -13
-4 9
100 20
4010 2
10 5810
-4 8
235 -2200

0 0

2
7