Задача 4. Частичная дефрагментация

Автор:А. Максимов, А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

Оперативная память компьютера имеет объём V байт, пронумерованных от 0 до V − 1. Выделенные блоки памяти задаются последовательностью адресов (a1, b1), (a2, b2), … (aN, bN). Блоки отсортированы по адресам и не перекрываются, т. е. 0 ≤ aibi < ai + 1 < V.

Операционная система пытается выделить память под ещё один блок объёмом M байт. Если свободное пространство такого размера отсутствует, она может попытаться переместить какой-нибудь один из блоков, чтобы освободить непрерывный участок нужной длины.

Требуется выбрать для перемещения блок наименьшей длины. Если таких вариантов несколько, следует выбрать блок с наименьшим начальным адресом.

Формат входного файла

Во входном файле расположены целые числа V N M. Далее идут N пар чисел ai bi.

Формат выходного файла

Выходной файл должен содержать единственное целое число:

Ограничения

0 ≤ N ≤ 100000, 1 ≤ V ≤ 1073741824

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10 2 4
1 5 7 7
2

0.025s 0.006s 15