TLE '17 Contest 8 P4 - Gamma Waves

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem types
Fax McClad with his trusted gamma wave oven.

Fax McClad, Croneria's most talented bounty hunter, is competing in a sandwich making competition!

Fax is required to make N sandwiches for the judges. The i^{th} sandwich is required to be made at time a_i. Fax can make sandwiches in 0 time.

All sandwiches are identical. In particular, the i^{th} judge is happy to get any sandwich, as long as the sandwich is delivered at time b_i.

However, sandwiches that are left in the open, waiting to be delivered, will rot. In particular, if a sandwich is left out in the open for more than X time units, it will become inedible.

In order to prevent this, Fax has a super powerful gamma wave oven that can zap one sandwich in 0 time, making it fresh again. That is, a zapped sandwich can now be left out for another X time units. The gamma wave oven can be used many times in the same time unit.

However, the gamma wave oven is expensive to use, so Fax wants to use it as little as possible. Can you tell Fax the minimum number of times he will need to use the gamma wave oven?


1 \le N \le 10^5

1 \le X \le 10^5

1 \le a_1 \le \dots \le a_N \le 10^9

1 \le b_1 \le \dots \le b_N \le 10^9

It is guaranteed that each judge can get a distinct sandwich. That is, a_i \le b_i for all 1 \le i \le N.

Subtask Percentage Additional Constraints
1 20 X = 1
2 20 N \le 8
3 20 N \le 2000
4 40 No additional constraints.

Input Specification

The first line of input will contain N and X.

N lines of input follow. The i^{th} line will contain a_i and b_i. It is guaranteed that a_i \le b_i, a_i \le a_{i+1}, b_i \le b_{i+1}.

Output Specification

On a single line, output the minimum number of times Fax needs to use the gamma wave oven.

Sample Input

5 10
1 1
2 32
12 33
50 61
51 70

Sample Output


Explanation for Sample Output

Sandwich 1 should be given to judge 1.

Sandwich 2 should be zapped at time 12 and time 22, then given to judge 2.

Sandwich 3 should be zapped at time 22 and time 32, then given to judge 3.

Sandwich 4 should be zapped at time 60, then given to judge 5.

Sandwich 5 should be given to judge 4.

In total, 5 zaps were needed.


There are no comments at the moment.