Redemption

The MAPS team has been working hard to create problems for the MAPS Beginner Competition.

Currently, there are $n$ team members working on problem creation. In the final team meeting before the competition, which starts at time 1 and ends at time $m$, each member $i$ is assigned a time interval $[l_i, r_i]$, during which they present their problems to Indra (a.k.a. the big boss). Here, $l_i$ and $r_i$ are natural numbers.

Unfortunately, Parsa has forgotten the exact time slot in which he was supposed to present his problems. However, he noticed an important rule in the meeting handbook: for every pair of team members, there must be at least one point during the meeting where both are presenting simultaneously.

Now, Parsa wonders how many possible time intervals $[l, r]$ he could have had for his presentation while still satisfying this rule - meaning that for every other team member, there exists at least one time point $t$ within $[l, r]$ where they are also presenting.

Note that:

1. Intervals can be 0-length ($[1, 1]$ is a valid interval).
2. Two intervals overlap, even if their intersection is a singular point in time ($[1, 2]$ and $[2, 3]$ overlap).

Input

The first line of input contains $n$ and $m$: the number of team members including Parsa and how long the meeting lasted.

The next $n - 1$ lines each contain two integers $l_i, r_i$ which are the intervals the $i$th person is presenting.

Output

Print the number of ways Parsa can choose an interval which holds the rule.

Constraints

• $2 \le n \le 200000$
• $1 \le m \le 200000$
• $1 \le l_i \le r_i \le m$

Example 1

2 4
3 4

7

Explanation

The other member presents on $[3, 4]$. There are $10$ intervals inside $[1, 4]$, and the three that miss $[3, 4]$ are $[1, 1]$, $[1, 2]$, and $[2, 2]$. The remaining $7$ all overlap $[3, 4]$.

Example 2

2 2
1 1

2

Explanation

Parsa must overlap $[1, 1]$. The valid choices are $[1, 1]$ and $[1, 2]$. The interval $[2, 2]$ does not overlap $[1, 1]$.