Description

Given $n$ points on the plane, find an axis-aligned rectangle whose boundary contains as many points as possible.

Input Format

The first line contains an integer $n$, the number of points in the plane. Each of lines $2\sim n+1$ contains two integers, the $x$- and $y$-coordinates of a point.

Output Format

Output a single integer: the maximum number of points that can lie on the boundary of the chosen rectangle.

10
2 3
9 2
7 4
3 4
5 7
1 5
10 4
10 6
11 4
4 6

7

Hint

Constraints and Notes

• For $40\%$ of the data, $1 \le n \le 30$.
• For $100\%$ of the data, $1 \le n \le 300$, and each coordinate lies in the range $[1,100]$.

Translated by ChatGPT 5