Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Beautiful fountains rows

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputButler Ostin wants to show Arkady that rows of odd number of fountains are beautiful, while rows of even number of fountains are not.

The butler wants to show Arkady *n* gardens. Each garden is a row of *m* cells, the *i*-th garden has one fountain in each of the cells between *l*_{i} and *r*_{i} inclusive, and there are no more fountains in that garden. The issue is that some of the gardens contain even number of fountains, it is wrong to show them to Arkady.

Ostin wants to choose two integers *a* ≤ *b* and show only part of each of the gardens that starts at cell *a* and ends at cell *b*. Of course, only such segments suit Ostin that each garden has either zero or odd number of fountains on this segment. Also, it is necessary that at least one garden has at least one fountain on the segment from *a* to *b*.

Help Ostin to find the total length of all such segments, i.e. sum up the value (*b* - *a* + 1) for each suitable pair (*a*, *b*).

Input

The first line contains two integers *n* and *m* (1 ≤ *n*, *m* ≤ 2·10^{5}) — the number of gardens and the length of each garden.

*n* lines follow. The *i*-th of these lines contains two integers *l*_{i} and *r*_{i} (1 ≤ *l*_{i} ≤ *r*_{i} ≤ *m*) — the bounds of the segment that contains fountains in the *i*-th garden.

Output

Print one integer: the total length of all suitable segments.

Examples

Input

1 5

2 4

Output

23

Input

3 6

2 4

3 6

4 4

Output

19

Note

In the first example the following pairs suit Ostin: (*a*, *b*): (1, 2), (1, 4), (1, 5), (2, 2), (2, 4), (2, 5), (3, 3), (4, 4), (4, 5).

In the second example the following pairs suit Ostin: (*a*, *b*): (1, 2), (1, 5), (2, 2), (2, 5), (3, 3), (4, 4), (4, 6), (5, 5), (6, 6).

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/10/2018 02:08:41 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|