D. Trick or Treat
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

It's Halloween, and you are on a quest to collect candies! The candies are scattered at various points in a 2D plane. You start at the origin $$$(0, 0)$$$, and you can collect the candies by traveling in a straight line. You want to maximize the number of candies you can collect in a single trip, and the condition is that all the candies you collect must lie on the same straight line passing through the origin.

Given $$$n$$$ candies, each located at distinct coordinates $$$(x_i, y_i)$$$, your task is to determine the maximum number of candies you can collect by traveling in one straight line.

Input

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of candies. The next $$$n$$$ lines each contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^9 \leq x_i, y_i \leq 10^9$$$) — the coordinates of the $$$i$$$-th candy. It is guaranteed that no candy is at the origin.

Output

Output a single integer, the maximum number of candies you can collect by traveling along a single straight line passing through the origin.

Example
Input
5
2 1
4 2
6 3
8 4
10 5
Output
5