Box Packing

Time limit1sMemory limit256 MB

Summary

Given n boxes as ordered pairs, select the most boxes that can be split into at most k chains, where each chain is nondecreasing in both coordinates.

Level: Hard8 of 10
Topics: Dynamic programming, Sorting, Greedy, Binary search
Solved: No attempts yet

Problem

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 you can select from them and split into no more than $k$ chains. You can reorder the boxes to form chains.

Input

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$ ).

Output

Print one integer: the answer.

Examples2

Example 1
Input
```
4 1
2 2
4 2
3 4
5 5
```
Expected output
```
3
```
Example 2
Input
```
4 2
2 2
4 2
3 4
5 5
```
Expected output
```
4
```