24674번 - Box Packing 다국어

문제

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.

제한

힌트