Processing math: 100%
4D longest path - MarisaOJ: Marisa Online Judge

4D longest path

Time limit: 1000 ms
Memory limit: 256 MB

In a four-dimensional space, there are n points xi=(ai,bi,ci,di). It’s possible to move from point xi to point xj if ai≀aj, bi≀bj, ci≀cj, and di≀dj. Find the longest path passing through each point at most once. You can start from any point.

Input

  • The first line contains an integer n.
  • The next n lines each contain four integers ai,bi,ci,di.

Output

  • Print an integer, the maximum number of points that can be visited.

Constraints

  • 1≀n≀5Γ—104.
  • 1≀ai,bi,ci,di≀109.

Example

Input:

3
2 3 4 4
1 2 3 4
2 2 1 3

Output:

2