Problem F
Arcaea Partners

The Arcaea game showing a list of partners

In the rhythm game Arcaea, the player can play songs with various partners. Every partner has two skill levels: Frag, and Step. A larger Frag allows playing songs to earn a larger number of fragments, the main resource of the game. A larger Step helps the player progress faster in the World Mode that unlocks new songs and game stories. Some of the partners can optionally be awakened. After being awakened, a partner’s Frag and Step both reach a higher level.

A keen player of Arcaea is likely to have obtained many partners. But as one can only be accompanied by one partner when playing songs, partners with higher Frag and Step values are generally favored. We say a partner $x$ is more favorable than another partner $y$, if $x$’s Frag value is strictly larger than $y$’s Frag value, and $x$’s Step value is strictly larger than $y$’s Step value. Additionally, for a set $S$ of partners we define $d(S)$, the diversity of $S$, to be the maximum number of partners one can choose from $S$, so that no chosen partner is more favorable than another chosen partner.

Seine is an Arcaea player who has a set $S$ of $n$ unawakened partners. Seine wants to choose at most $k$ partners to awaken to maximize $d(S)$. What is the maximum $d(S)$ she can achieve?

Input

The first line of the input has two integers $n$ and $k$ ($1 \leq k \leq n \leq 2\, 000$). The next $n$ lines each have four integers $g, p, g_ a, p_ a$ to describe one partner’s skill levels. The first two integers $g, p$ are the partner’s Frag and Step values before being awakened ($1 \leq g, p \leq 10^9$). The last two integers $g_ a, p_ a$ are zeroes if the partner cannot be awakened. Otherwise $g_ a, p_ a$ give the partner’s new Frag and Step values after being awakened, and it is guaranteed that $g < g_ a \leq 10^9$ and $p < p_ a \leq 10^9$.

Output

Output the maximum $d(S)$ Seine can achieve, if she can awaken up to $k$ partners. Note that Seine may choose to not awaken any partner.

Note

Arcaea is created and developed by Lowiro Limited. Lowiro does not endorse and has no involvement with the ProgNova contest.

6 1
78 61 88 71
80 80 90 90
70 90 80 100
90 70 0 0
80 67 0 0
90 63 0 0

5

5 5
50 70 80 80
60 60 90 90
70 50 100 100
50 50 70 70
50 50 70 70

4