LCC '21 Contest 6 J5 - Bob's Carnival Tour

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Bob enters a carnival, with locations depicted by a cartesian coordinate system. He enters at (0, 0). There are N attractions around the carnival, each at a location (x, y). Due to his time being limited, Bob wants to try and visit as many attractions as possible in the M minutes he has. It takes 1 minute to travel a distance of 1 on the cartesian coordinate system and 0 minutes to view an attraction. Bob can end his M minutes anywhere in the carnival. In addition, he also wants to see as much variety as possible so he avoids visiting the same attraction twice. Given the locations of the attractions, can you determine what the most attractions he can visit in M minutes is?

Note that the distance between two attractions is calculated as \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}.

Input Specification

The first line will contain two integers, N (1 \leq N \leq 5) and M (1 \leq M \leq 10^8).

The next N lines will contain two integers each, the x (0 \leq x \leq 10^3) followed by y (0 \leq y \leq 10^3) position of an attraction, separated by a space.

Output Specification

Output the maximum number of attractions Bob can visit.

Sample Input 1

3 100
5 160
100 10
5 5

Sample Output 1

1

Sample Input 2

5 100
1 1
2 2
10 10
80 80
90 90

Sample Output 2

3

Comments

There are no comments at the moment.