Longest Monotonic Path in 4D Space

In this problem, you are given n points in a 4-dimensional space. Each point is represented by four coordinates. Your task is to determine the maximum number of points that form a path such that for each of the four coordinates, the sequence is non-decreasing.

More formally, given points \(P_i = (x_i, y_i, z_i, w_i)\) for \(1 \le i \le n\), you need to find the longest sequence of distinct indices \(i_1, i_2, \ldots, i_k\) so that for every dimension and for every \(1 \leq j < k\) the following holds:

[ x_{i_j} \leq x_{i_{j+1}}, \quad y_{i_j} \leq y_{i_{j+1}}, \quad z_{i_j} \leq z_{i_{j+1}}, \quad w_{i_j} \leq w_{i_{j+1}}. ]

The path can begin from any point and the ordering of the points in the input does not necessarily correspond to their order in the path. The length of a path is defined by the number of points used.

inputFormat

The first line contains an integer n, the number of points.

Each of the following n lines contains four space-separated integers representing the coordinates of a point.

Constraints: It is guaranteed that the input is such that a valid solution exists under the constraints of standard programming contest problems.

outputFormat

Print a single integer, the maximum length of a path that can be constructed where the coordinates in each dimension are non-decreasing.

sample

5
1 2 3 4
2 3 4 5
3 3 3 3
2 2 2 2
4 5 6 7

3