Cossack Vus and Segments#10486

Cossack Vus and Segments

2 seconds

256 megabytes

Easy

Cossack Vus has discovered $n$ segments on a coordinate line. Each segment is defined by two coordinates: $a_{i}$ a_i as the starting point and $b_{i}$ b_i as the ending point.

He wants to add two new segments, each of length $m$ , in such a way that these two segments do not overlap. Let $x$ represent the number of original segments that completely contain the first new segment, and $y$ represent the number of original segments that completely contain the second new segment.

Cossack Vus aims to position these two segments to maximize the sum $x + y$ x+y. Your task is to help him determine this maximum value.

Note that a single original segment can completely contain both new segments at the same time.

Note 1. If $k_{1}$ k_1 and $k_{2}$ k_2 ( $k_{1} < k_{2}$ k_1 < k_2) are the starting points of the new segments, then the segments do not overlap if $k_{1} + m \leq k_{2}$ k_1 + m \le k_2.

Note 2. A new segment starting at $k$ is completely contained within an original segment $[l, r]$ [l, r] if $l \leq k$ l \le k and $k + m \leq r$ k + m \le r.

Input

The first line contains two integers $n$ and $m$ ( $1 \leq n \leq 3 \cdot 1 0^{5}, 1 \leq m \leq 1 0^{8}$ 1 \le n \le 3 \cdot 10^5, 1 \le m \le 10^8) — the number of original segments and the length of the new segments.

Each of the following $n$ lines contains two integers $a_{i}, b_{i}$ a_i, b_i ( $1 \leq a_{i} < b_{i} \leq 1 0^{8}$ 1 \le a_i < b_i \le 10^8) — the start and end coordinates of each original segment.

Output

Output a single integer — the maximum possible value of $x + y$ x+y.

Examples

Example 1

Loading

Scoring

( $10$ points): $n, m, a_{i}, b_{i} \leq 200$ n, m, a_i, b_i \le 200;
( $10$ points): $n \leq 200$ n \le 200;
( $20$ points): $n \leq 2000$ n \le 2000;
( $20$ points): $n \leq 2 \cdot 1 0^{5}, m = 1$ n \le 2 \cdot 10^5, m=1;
( $40$ points): no additional constraints.

a_{i}

b_{i}

x + y

k_{1}

k_{2}

k_{1} < k_{2}

k_{1} + m \leq k_{2}

[l, r]

l \leq k

k + m \leq r

1 \leq n \leq 3 \cdot 1 0^{5}, 1 \leq m \leq 1 0^{8}

a_{i}, b_{i}

1 \leq a_{i} < b_{i} \leq 1 0^{8}

x + y

n, m, a_{i}, b_{i} \leq 200

n \leq 200

n \leq 2000

n \leq 2 \cdot 1 0^{5}, m = 1