Задача 31. Пиф-Паф! ≡

Условие

Раз, два, три, четыре, пять,

Вышел зайчик погулять;

Вдруг охотник прибегает

Из ружья в него стреляет..,

Пиф-Паф! Ой-ой-ой!

Умирает зайчик мой!

Фёдор Миллер, "Раз, два, три, четыре, пять...", 1851 г.

На координатной прямой притаились три охотника. Каждый из них обладает своей зоной обзора и способен обнаружить зайца, если тот находится на прямой в пределах некоторого непрерывного отрезка, включая границы. Эти отрезки могут вырождаться в точки (охотник смотрит себе под ноги) и пересекаться или даже совпадать для различных охотников. Зайчик обладает параметром "ловкость", которая может принимать значение от 0 до 2. Если количество охотников, заметивших зверька, превысит ловкость зайца, они его подстрелят. По входным данным определите количество опасных для зайца точек координатной прямой с целыми координатами.

Формат входных данных

Первые три строки входного файла содержит по два целых числа, записанных через пробел: l_i и r_i — начало и конец отрезка зоны обзора для очередного охотника. В последней строке расположено неотрицательное целое число a — ловкость зайца.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

Формат выходных данных

Выведите одно неотрицательное целое число — количество различных точек координатной прямой с целочисленными координатами, принадлежащих более чем a отрезкам из трёх.

Ограничения

 − 10¹⁵ ≤ l_i, r_i ≤ 10¹⁵

0 ≤ a ≤ 2

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при  − 10⁵ ≤ l_i, r_i ≤ 10⁵, получат не менее 50 баллов.

Пояснение к примерам

Смотри верхний рисунок для 1-3 примеров, нижний — для 4-го примера.

В первом примере для зайца опасными являются точки с координатами от 0 до 11.

Во втором первом примере для зайца опасными являются точки с координатами от 2 до 10.

В третьем первом примере для зайца опасными являются точки с координатами от 4 до 7.

В четвёртом примере для зайца опасна единственная точка 4.

Примеры тестов

0 7
2 11
4 10
0

12

0 7
2 11
4 10
1

9

0 7
2 11
4 10
2

4

0 7
8 9
4 4
1

1