Description

One day, while Cool and touli were participating in a multi-school contest, they started discussing what kind of lineup would be strong. Cool thought that in a lineup, after sorting heroes by level from low to high, their attack values should be increasing. Cool then asked touli what the maximum possible size of such a lineup would be.

However, touli felt this question was too trivial, so he changed the condition: after sorting by level from low to high, for any two adjacent heroes in this order, the lower-level hero’s attack must be no greater than the higher-level hero’s strength, and the higher-level hero’s attack must be no less than the lower-level hero’s intelligence.

Now Cool wants to know, among several heroes, what is the maximum number of heroes that can be selected to form such a lineup.

Input Format

The first line $n$ indicates there are $n$ heroes.

The next $n$ lines each contain $4$ integers $l, s, w, a$, representing that hero’s level, strength, intelligence, and attack, respectively.

Output Format

A single integer, the maximum number of heroes that can be selected.

3
1 2 3 1
2 1 2 2
3 1 3 3

2

Hint

Selecting the $1$st and $3$rd heroes satisfies the condition. For the $1$st and $2$nd heroes, the $2$nd hero’s attack is less than the $1$st hero’s intelligence, so they cannot both be in the lineup.

Constraints: $n \leq 10^5$, $l, s, w, a \le 10^8$, and the $l$ values are pairwise distinct.

Translated by ChatGPT 5