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

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

 − 1015 ≤ li, ri ≤ 1015

0 ≤ a ≤ 2

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

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

Решения, верно работающие при  − 105 ≤ li, ri ≤ 105, получат не менее 50 баллов.

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

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

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

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

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

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

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

Стандартный вход Стандартный выход
1
0 7
2 11
4 10
0
12
2
0 7
2 11
4 10
1
9
3
0 7
2 11
4 10
2
4
4
0 7
8 9
4 4
1
1

0.140s 0.020s 17