시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB38191959.375%

문제

An ordered pair of integers $(x, y)$ is called a box. A sequence of boxes $(c_1, d_1), \ (c_2, d_2), \ \ldots, \ (c_m, d_m)$ is called a chain if the following inequalities hold: $$ c_1 \le c_2 \le \ldots \le c_m , \quad d_1 \le d_2 \le \ldots \le d_m \text{.} $$

You are given $n$ boxes: $(a_1, b_1), \ (a_2, b_2), \ \ldots, \ (a_n, b_n)$. Find the maximum number of boxes that you can select from them and split into no more than $k$ chains. You can reorder the boxes to form chains.

입력

The first line contains two integers, $n$ and $k$ ($1 \le n \le 10^5$, $1 \le k \le 100$).

The $i$-th of the following $n$ lines contains two integers, $a_i$ and $b_i$ ($1 \le a_i, \ b_i \le 10^9$).

출력

Print one integer: the answer.

예제 입력 1

4 1
2 2
4 2
3 4
5 5

예제 출력 1

3

예제 입력 2

4 2
2 2
4 2
3 4
5 5

예제 출력 2

4