T406803

【Dib-3】E 偷工减料 (Hard version)

题目背景

Dacong 很慌，因为他原本用来要压岁钱的时间不多了。神奇的是，他完成作业《启航》的时间也不多了。看着自己动不动就罢工的笔，Dacong 自然想到了偷工减料。

题目描述

自然，偷工减料过头会被制裁。

所以 Dacong 发现，这些题目可以划分为 $n$ 个部分，每个部分中至少只要有 $k$ 道题认真完成才可以蒙混过关。

否则：

天理会降下劫罚。

Dacong 不想认真做太多题目，所以他请你计算一下，他最少认真做多少道题即可蒙混过关。

输入格式

第一行两个数，表示 $n,k$。

接下来 $n$ 行，每行两个数 $l,r$。

输出格式

一行一个数，表示答案。

样例 #1

样例输入 #1

5 2
2 4
4 7
4 9
6 10
1 10

样例输出 #1

4

提示

数据保证 $l \le r$，$k \le r-l+1$，数据皆为整数。

对于 $10 \%$ 的数据，$k = 1$。

对于 $100 \%$ 的数据，$1 \le n \le 10^6,1 \le k \le n,1 \le l,r \le 10^6$。

这是我们自己团队内部的月赛题，结果出题组蒟蒻们一个都不会都懒得做，有大佬能给出正解吗