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

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

Условие

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

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

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

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

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

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

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

Ограничения

0 &le; N &le; 100000, 1 &le; V &le; 1073741824

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

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

0.104s 0.011s 13