ВШ. ДЗ 1. ДП - Частичная дефрагментация

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

задачи
видимые пробелы
простые формулы
широкий текст
редактор

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

Условие

Оперативная память компьютера имеет объём V байт, пронумерованных от 0 до V − 1. Выделенные блоки памяти задаются последовательностью адресов (a₁, b₁), (a₂, b₂), … (a_N, b_N). Блоки отсортированы по адресам и не перекрываются, т. е. 0 ≤ a_i ≤ b_i < a_{i + 1} < V.

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

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

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

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

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

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

номер блока, который нужно перемещать;
0, если блоки перемещать не нужно (непрерывный участок нужного объёма есть сразу);
−1, если решения нет (пространство нужного объёма освободить не удаётся).

Ограничения

0 ≤ N ≤ 100000, 1 ≤ V ≤ 1073741824

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

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