Layer Selection with Multiple Intervals - EP1

Version: Phuoc Hung OJ Extended

Problem Statement

Positions are numbered by the positive integers $1,2,3,\ldots$.

For each positive integer $k$, a position $x$ belongs to layer $k$ if and only if

Thus every position belongs to exactly one layer.

You are given a position interval $[L,R]$ and $N$ layer intervals $[A_i,B_i]$. A position $x$ is selected if the index of its layer belongs to at least one of the given layer intervals. The intervals may overlap, contain one another, or be adjacent.

Count the selected positions in $[L,R]$. Each position is counted once even if its layer is covered by several intervals.

Input

• The first line contains three integers $L,R,N$.
• The next $N$ lines each contain two integers $A_i,B_i$, describing the $i$-th layer interval.

Output

Print one integer: the number of selected positions $x \in [L,R]$.

Subtasks

• Subtask 1 (25 points): $N \le 100$ and $R-L \le 10^5$.
• Subtask 2 (30 points): $R-L \le 10^6$.
• Subtask 3 (45 points): $1 \le L \le R \le 10^{18}$, $1 \le N \le 2\cdot10^5$, $1 \le A_i \le B_i \le 10^9$.

Examples

Example 1

Input

1 20 2
2 2
3 3

Output

12

Explanation

Layer 2 covers positions 4 through 8 and layer 3 covers positions 9 through 15. Together they form $[4,15]$, which contains 12 positions.

Example 2

Input

10 30 2
4 4
2 2

Output

9

Explanation

Layer 2 is $[4,8]$ and does not intersect $[10,30]$. Layer 4 is $[16,24]$, so all 9 positions of that layer are counted.

Example 3

Input

1 100 3
2 4
4 6
8 8

Output

62

Explanation

The intervals $[2,4]$ and $[4,6]$ overlap, so together they cover layers 2 through 6. These layers correspond to positions $[4,48]$, containing 45 positions. Layer 8 corresponds to $[64,80]$, containing 17 more positions. The total is $45+17=62$.

Example 4

Input

50 70 2
1 3
8 10

Output

7

Explanation

Layers 1 through 3 end before position 50. Layers 8 through 10 start at 64, so only $[64,70]$ contributes, which contains 7 positions.

Example 5

Input

1000000000000000000 1000000000000000000 1
1000000000 1000000000

Output

1

Explanation

$10^{18}=(10^9)^2$, so the only position in the interval belongs to layer $10^9$ and is counted once.