시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 38 | 19 | 19 | 59.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.
4 1 2 2 4 2 3 4 5 5
3
4 2 2 2 4 2 3 4 5 5
4