Let's Shoot an Arrow!

Interview

Time limit1sMemory limit1024 MB

Summary

Given N points, find the maximum number that lie on a single ray starting from the origin.

Level: Medium4 of 10
Topics: Hash map, Math, Geometry, Sorting
Solved: No attempts yet

Problem

Hojun has recently gotten hooked on archery. After practicing hard, he reached the point where every shot he fires scores 10 points. Tired of shooting at a target that sits in one direction, he decided to try a new kind of archery.

Unlike the usual format where the score depends on where the arrow lands, balloons are placed at points (x, y) on a wide two-dimensional field, and he shoots an arrow from the designated position (0, 0) in whatever direction he wants. The arrow travels infinitely far along its direction, and the score he earns equals the number of balloons the arrow pops as it flies. Each balloon is worth the same 1 point, and no two balloons share the same position. A balloon also cannot be placed at (0, 0), where Hojun stands.

Hojun carefully chose a direction and fired one shot, then wondered whether the direction he picked was the best one. He wants to know the maximum score he can get with a single arrow. Given the positions of the balloons, find the highest score he can earn by shooting one arrow, on behalf of Hojun, who is busy practicing archery.

Input

The first line contains the number of balloons, the integer N (1 ≤ N ≤ 100,000).

The next N lines contain two integers x, y, the position of a balloon (-1,000,000 ≤ x, y ≤ 1,000,000).

Output

Print on the first line the maximum score that can be earned by shooting one arrow.

Examples2

Example 1
Input
```
5
8 16
10 -3
2 4
7 10
1 2
```
Expected output
```
3
```

Example 2

Input

Expected output