F. Красивые ряды фонтанов
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дворецкий Остин хочет показать Аркадию, что ряды из нечетного числа фонтанов — это красиво, а ряды из четного числа фонтанов — нет.

Дворецкий хочет показать Аркадию n садов. Каждый сад представляет из себя ряд из m клеток, в i-м из садов в каждой клетке с li по ri включительно находится фонтан, и больше фонтанов в этом саду нет. Проблема в том, что некоторые из садов все-таки имею четное число фонтанов, что недопустимо показывать Аркадию.

Остин хочет выбрать два числа a ≤ b и показать из каждого сада лишь участок, начинающийся в клетке a и кончающийся в клетке b. Конечно, подойдут лишь такие участки, что в каждом саду на этом отрезке либо нет фонтанов, либо нечетное число фонтанов. Кроме того, необходимо, чтобы хотя бы в одном саду на участке клеток от a до b был хотя бы один фонтан.

Помогите Остину найти суммарную длину всех таких участков, то есть, просуммируйте величину (b - a + 1) для каждой подходящей пары (a, b).

Входные данные

В первой строке находятся два целых числа n и m (1 ≤ n, m ≤ 2·105) — число садов и длина каждого сада.

Далее следуют n строк. В i-й из этих строк находятся два целых числа li и ri (1 ≤ li ≤ ri ≤ m) — границы участка, на котором в саду номер i есть фонтаны.

Выходные данные

Выведите одно число — суммарную длину всех подходящих участков.

Примеры
Входные данные
1 5
2 4
Выходные данные
23
Входные данные
3 6
2 4
3 6
4 4
Выходные данные
19
Примечание

В первом примере подходят следующие пары (a, b): (1, 2), (1, 4), (1, 5), (2, 2), (2, 4), (2, 5), (3, 3), (4, 4), (4, 5).

Во втором примере подходят следующие пары (a, b): (1, 2), (1, 5), (2, 2), (2, 5), (3, 3), (4, 4), (4, 6), (5, 5), (6, 6).