Minimum Connected Delivery Zones After Adding One Interval

There are existing closed-interval delivery zones, which may overlap. You must add exactly one closed interval [a,b], whose length is defined as b−a; the length may be 0 and must not exceed k. Intervals are connected only when they share a point; adjacent integers do not count as connected. Find the minimum number of connected components after the addition. The original statement explicitly says [2,2] and [3,4] are not connected, and the continuous-interval semantics are restored from that.

输入格式

The first line contains n k, followed by n lines each containing a[i] b[i]. 1≤n≤100000, 1≤a[i]≤b[i]≤10^9, 1≤k≤10^9.

输出格式

Output a single integer, the answer.

样例 1

输入：

5 2
1 5
2 4
6 6
7 14
16 19

输出：

2

样例 2

输入：

4 2
1 2
2 4
5 8
10 11

输出：

2

样例 3

输入：

3 4
1 1
3 3
5 5

输出：

1

样例说明

The answers are 2, 2 and 1 respectively. In the third example a single [1,5] connects three components at once; it is not limited to connecting two at a time.