A telecom crew has already buried n separate fiber-optic cable segments along a single straight utility trench, each described by the meter marks where it begins and ends. The segments are listed in order of increasing start position, and no two of them touch or overlap, so right now the trench holds exactly n separate connected clusters of cable.

The crew has one more spool of cable, of a fixed length k, that they can splice into the trench as a brand-new segment [x, x + k] for any integer x of their choosing -- x may be negative, may land inside an already-clustered stretch with no benefit, or may bridge across an empty gap between two existing segments. Two segments (original or newly spliced) belong to the same cluster whenever their ranges overlap or merely touch at a single point, and this connectivity is transitive: if segment A shares a cluster with B, and B shares a cluster with C, then A, B, and C all belong to one cluster.

Decide where to splice the new segment so that, after splicing, the trench contains as few distinct connected clusters as possible, and report that minimum number of clusters.

Input format

• Line 1: two integers n and k.
• Each of the next n lines: two integers start_i and end_i, describing one existing cable segment.
• The segments are given sorted by start_i, and are guaranteed pairwise disjoint with a strictly positive gap between consecutive segments: end_i < start_{i+1} for every 1 <= i < n.

Output format

Print a single integer: the minimum possible number of connected clusters after splicing in exactly one new segment of length k.

Constraints

• 1 <= n <= 10^5
• 0 <= k <= 10^9
• -10^9 <= start_i <= end_i <= 10^9
• end_i < start_{i+1} for every 1 <= i < n

3 3
1 2
5 6
10 12

2

2 9
0 1
10 11

1