链接: https://cses.fi/problemset/task/1632

板块: Sorting and Searching

时限: 1.00 s ｜ 内存: 512 MB

题目描述

某电影节将放映 $n$ 部电影。Syrjälä 的电影俱乐部由 $k$ 名成员组成，他们都将参加电影节。

你知道每部电影的起止时间。如果采取最优策略，俱乐部成员总共最多能完整地观看多少部电影？

输入

第一行包含两个整数 $n$ 和 $k$：电影数量和俱乐部成员数。

之后有 $n$ 行描述电影。每行包含两个整数 $a$ 和 $b$：某部电影的起止时间。

输出

输出一个整数：总共能观看的最多电影数量。

数据范围

$1 \le k \le n \le 2 \cdot 10^5$ $1 \le a < b \le 10^9$

样例输入

5 2
1 5
8 10
3 6
2 5
6 9

样例输出

4