Party Location

Interview

Time limit1sMemory limit128 MB

Summary

Given up to 200 house coordinates in a 50 km square, find a party location within 2.5 km of as many houses as possible.

Level: Medium7 of 10
Topics: Geometry, Brute force, Math, Sorting
Solved: No attempts yet

Problem

After the programming contest, all of the contestants would like to throw a party. But afterwards it will be late, and the contestants will be too tired to walk far. Specifically, a contestant refuses to come if the party is more than 2.5 km from their house (exactly 2.5 km is acceptable).

So the party should be held as close as possible to as many houses as possible. Your job is to determine the optimal location for the party so that as many contestants as possible are willing to attend.

The city is a flat square, 50 km on each side. A contestant can walk in a straight line directly from the party to their house (there are no obstacles).

Input

Input consists of a number of lines, each containing two floating-point numbers giving the $(x, y)$ coordinates of one contestant's house. Each coordinate is between $0.0$ and $50.0$ (km) and is given with at most four digits after the decimal point. Every house is at a distinct location. There are at most 200 contestants. Read until end of input.

Output

Output a single integer: the maximum number of contestants that can attend the party.

Examples2

Example 1

Input

4.0 4.0
4.0 5.0
5.0 6.0
1.0 20.0
1.0 21.0
1.0 22.0
1.0 25.0
1.0 26.0

Expected output

Example 2
Input
```
10.0 10.0
```
Expected output
```
1
```