Easter Eggs

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 minimize 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 (where he is currently located), 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 carrying eggs. What complicates matters is that the sun rises at different times depending on where you are in the flat world! At coordinate (x, y), the sun rises 720 + x/2000 minutes after midnight. Note that the Easter Bunny only needs to deliver an egg before the sun rises at the place where the egg should be delivered, and that it is ok if the sun rises during his journey home. When traveling 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 a time he has keeping his pace up. When not carrying any eggs, the Easter Bunny can move (jump) at a speed of v meters 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 · 2−i meters per second. Since we are already running on a tight schedule, we don’t bother modeling 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 less than 32 test cases. The first line of a test case contains two integers 1 ≤ n ≤ 17, 1 ≤ v ≤ 100, where n is the number of eggs to be delivered and v is Easter Bunny’s velocity when he carries zero eggs. Then follow n lines, each containing two integers x and y, indicating where to deliver the n eggs. The Easter Bunnys secret hideout is located at x = 0, y = 0. The length unit of the coordinates is meters, and you may assume that all coordinates have absolute value bounded by 106. 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. Sample Input 45 -42000 0 0 42000

2/2 42000 0 0 -42000 81 50 8 -4711 -13 -4 9 100 20 4010 2 10 5810 -4 8 235 -2200 00 Sample Output 2 7