Fruit Slicer

Time limit2sMemory limit512 MB

Summary

Given up to 100 unit circles, find the maximum number that a single infinite line can intersect, counting tangency as a hit.

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

Problem

John, a student taking the game development course, recently developed a mobile game called Fruit Slicer for his coursework. In the game the player slices fruits that are thrown into the air by swiping the touch screen. However the game is quite simple because John was not able to write code for the geometry required for a more complex version. In the game each slice is a straight line of infinite length, and all fruits have the same shape of a circle with unit radius. The figure shows a cool snapshot of John's game.

John introduces his game to his best friend Sean, who soon gets bored of playing the simple game. But as a teaching assistant of the algorithm course, Sean decides to turn the game into a homework assignment. He asks the students in the algorithms course to write a program that can compute the best slice at any given moment of the game. Given the locations of the fruits, the program should determine the maximum number of fruits that can be sliced with a single straight-line swipe.

As a student in Sean's class, you are now the one who is facing this challenge.

Input

The first line has a single integer n (1 ≤ n ≤ 100). The next n lines each have two real numbers giving the x and y coordinates of a fruit. All coordinates have an absolute value no larger than 10⁴ and are given with exactly two digits after the decimal point. Fruits may overlap.

Output

Output the maximum number of fruits that can be sliced with one straight-line swipe. A swipe slices a fruit if the line intersects the inner part or the boundary of the fruit.

Examples3

Example 1

Input

Expected output

Example 2
Input
```
3
-1.50 -1.00
1.50 -1.00
0.00 1.00
```
Expected output
```
3
```
Example 3
Input
```
2
1.00 1.00
1.00 1.00
```
Expected output
```
2
```