## TLE '17 Contest 8 P4 - Gamma Waves

View as PDF

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

Author:
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 sandwiches for the judges. The sandwich is required to be made at time . Fax can make sandwiches in time.

All sandwiches are identical. In particular, the judge is happy to get any sandwich, as long as the sandwich is delivered at time .

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 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 time, making it fresh again. That is, a zapped sandwich can now be left out for another 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?

#### Constraints

It is guaranteed that each judge can get a distinct sandwich. That is, for all .

#### Input Specification

The first line of input will contain and .

lines of input follow. The line will contain and . It is guaranteed that , , .

#### 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

5

#### Explanation for Sample Output

Sandwich should be given to judge .

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

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

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

Sandwich should be given to judge .

In total, zaps were needed.