题目背景

辐射是有距离的

题目描述

农场主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)\)。