P14090 [ICPC 2023 Seoul R] Lucky Draws

ICPC 组委会计划举办一个惊喜活动，为参赛队伍加油助威。组委会在比赛前为每支队伍提供一对数 $A$ 和 $B$（$A\le B$），用于赛后抽奖。组委会计划举办 $K$ 次抽奖。每一次抽奖，组委会选择一个数字 $C$，所有满足 $A\le C\le B$ 的队伍在本次抽奖中获奖。为了让更多队伍获奖，组委会希望提前选好 $K$ 个用于抽奖的数字，使最多队伍获奖。一个队伍可以多次获奖，但只计为一次。 例如，有五支队伍参加 ICPC，队伍的数字对分别为 $(1,2), (1,4), (3,6), (4,7), (5,6)$，且 $K=2$。当组委会选择数字 $2$ 和 $4$ 时，$4$ 支队伍 $(1,2), (1,4), (3,6), (4,7)$ 获奖。队伍 $(1,4)$ 因包含两个数字而获奖两次，但只计一次。实际上，选择 $2$ 和 $5$ 时，所有五支队伍都能获奖。最大获奖队伍数为 $5$。 给定 $n$ 个队伍的整数对以及抽奖次数 $K$，请编程输出能获奖的最大队伍数。

你的程序需要从标准输入读取数据。第一行为两个整数 $n$ 和 $K$（$1\le n\le 10\,000,\ 1\le K\le n,\,1\le n\times K\le 500\,000$），其中 $n$ 表示队伍数量，$K$ 表示抽奖次数。接下来的 $n$ 行每行包含两个整数 $A$ 和 $B$，代表某支队伍的数字对，$-10^6\le A\le B\le 10^6$。

你的程序需要向标准输出输出一行。该行包含一个整数，表示最多有多少支队伍能获奖。多次获奖的队伍只算一次。

由 ChatGPT 5 翻译