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 200 000~
• ~1 \le m \le 200 000~
• ~1 \le l_i \le r_i \le m~

Example 1

Input

2 4
3 4

Output

7

Example 2

Input

2 2
1 1

Output

2