# Arcaea 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.

Sample Input 1 | Sample Output 1 |
---|---|

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 |

Sample Input 2 | Sample Output 2 |
---|---|

5 5 50 70 80 80 60 60 90 90 70 50 100 100 50 50 70 70 50 50 70 70 |
4 |