Coverage

Time limit3sMemory limit256 MB

Summary

Given towers with unit disk coverage, place one more disk to maximize the number of towers in one connected group.

Level: Medium7 of 10
Topics: Geometry, Union-find, Graph
Solved: No attempts yet

Problem

A cellular provider has installed $n$ towers. Each tower covers everything within 1 km of it, and no two towers are closer than 1 km to each other. The coverage region of the network is the set of all points that lie within 1 km of at least one tower.

The provider wants as much of this region as possible to be connected. Connected means that a user at any point of a connected subregion can travel to every other point of that subregion without leaving it. The towers already installed may or may not form a single connected region. The provider has the resources to build one more tower anywhere, including within 1 km of an existing tower.

Given that one more tower is built, what is the largest number of towers, counting the new one, that can lie inside a single connected subregion of the coverage?

Input

The first line contains one integer $n$ , the number of towers already installed. ( $1 \le n \le 5000$ )

Each of the next $n$ lines contains two space-separated real numbers $x_i$ and $y_i$ , the position of tower $i$ in km. ( $0 \le x_i, y_i \le 10^5$ )

The answer is guaranteed to stay the same even if the coverage radius of every tower is increased or decreased by one millimeter.

Output

Print on a single line one integer, the largest number of towers that can lie inside a single connected subregion of the network after one more tower is installed.

Examples2

Example 1

Input

5
1.0 1.0
3.1 1.0
1.0 3.1
3.1 3.1
4.2 3.1

Expected output

Example 2

Input

5
1.0 1.0
3.1 1.0
1.0 3.1
3.1 3.1
10.0 10.0

Expected output