[YT001B]辐射区间
题目背景
辐射是有距离的
题目描述
农场主Jone有一座农场,奶牛们被划分到 \(n\) 个区间里,第\(i\)个区间的左端点位置和右端点位置为\(a_i,b_i\),每个区间的奶牛每天都要吃 \(k\) 不同的饲料,每块地最多放一种饲料。给你\(a_1,a_2,a_3,...,a_n\) \(b_1,b_2,b_3,...,b_n\),请你告诉Jone他至少要买多少饲料。
输入格式
第一行 \(n\)和\(k\);
接下来 \(n\) 行,每行包括两个整数分别为 \(a_i,b_i\) 。
输出格式
输出一个整数,表示选出的最少买多少饲料。
样例 #1
样例输入 #1
6 1
6 26
19 27
20 28
16 35
43 45
26 40
样例输出 #1
2
样例 #2
样例输入 #2
5 4
334 610
509 969
909 926
639 842
834 920
样例输出 #2
12
提示
\(\tt{Subtask \ 0} \ 50\)% 数据,\(n≤3\ast 10^{6}\),\(0≤a≤b≤3\ast 10^{7},k\le min(b_i-a_i)(i\in n)\)。\
\(\tt{Subtask \ 1} \ 25\)% 数据,\(n≤4\ast 10^{6}\),\(0≤a≤b≤500,k\le min(b_i-a_i)(i\in n)\)。\
\(\tt{Subtask \ 2} \ 25\)% 数据,\(n≤5\ast 10^{6}\),\(0≤a≤b≤3000,k\le min(b_i-a_i)(i\in n)\)。