Description

Four-dimensional space is truly wonderful. Now there are $n$ points in four-dimensional space. Find a longest path such that, along the path, each coordinate in every dimension is monotonically non-decreasing.

Note that the starting point of the path can be chosen arbitrarily, and the path is independent of the input order (the order along the path does not need to be increasing in the input).

The length of a path is the number of points visited, and any point can be visited at most once.

Input Format

The first line contains an integer $n$. The next $n$ lines each contain four integers $a_i,b_i,c_i,d_i$, representing a 4D coordinate.

Output Format

Output one integer in a single line, the length of a longest path.

4
2 3 33 2333
2 3 33 2333
2 3 33 2333
2 3 33 2333

4

Hint

Let $m_i=\max(|a_i|,|b_i|,|c_i|,|d_i|),m=\max(m_i)$. | Test point index | $n\le$ | $m\le$ | Special note | | :----------: | :----------: | :----------: | :----------: | | $1$ | $2000$ | $10^9$ | | | $2$ | $5\times 10^4$ | $8$ | | | $3\sim 4$ | $5\times 10^4$ | $10^5$ | The 3rd and 4th coordinates of all points are the same | | $5\sim 6$ | $5\times 10^4$ | $10^5$ | The 4th coordinate of all points is the same | | $7\sim 8$ | $5\times 10^4$ | $100$ | | | $9\sim 10$ | $5\times 10^4$ | $10^9$ | |

Translated by ChatGPT 5