## APIO '19 P1 - Strange Device

View as PDF

Points: 20
Time limit: 1.8s
Memory limit: 512M

Problem type

Archaeologists have found a strange device that was probably created by some ancient civilization. The device has a screen that displays two integers: and .

After exploring the device the scientists have made a conclusion that the device is kind of a clock. It measures time passed from some moment in the past, but shows it in some weird way, probably used by the creators of the device. If the time passed is an integer , the two integers displayed are: , and . Here is the floor function — the greatest integer less or equal to .

The archaeologists have studied the device and found out that its screen wasn't turned on all the time. Actually it was only working during continuous periods of time, the -th of them was from the moment to the moment , inclusive. Now the scientists would like to calculate how many distinct pairs were shown by the device when its screen was on.

Two pairs and are distinct if or .

#### Input Specification

The first line contains three integers , , and (; ).

Each of the following lines contains two integers and , the beginning and the end of the -th segment when the device screen was turned on (; ).

#### Output Specification

Output the number of distinct pairs that were shown on the device screen when it was turned on.

Let and .

#### Sample Input 1

3 3 3
4 4
7 9
17 18

#### Sample Output 1

4

#### Sample Input 2

3 5 10
1 20
50 68
89 98

#### Sample Output 2

31

#### Sample Input 3

2 16 13
2 5
18 18

#### Sample Output 3

5

#### Explanation

In the first test, the device screen shows the following integers.

,

,

,

,

,

,

So there are four distinct pairs , , , .

• commented on Oct. 1, 2019, 6:10 p.m.

• commented on May 15, 2020, 2:15 a.m. edit 2

It's actually even smaller: fits inside a long long. ()