Дистанционный практикум по программированию

Оперативная память компьютера имеет объём V байт, пронумерованных от 0 до V-1. Выделенные блоки памяти задаются последовательностью адресов (a1, b1), (a2, b2), ... (aN, bN). Блоки отсортированы по адресам и не перекрываются, т. е. 0 <= a_i <= b_i < a_{i + 1} < V. Операционная система пытается выделить память под ещё один блок объёмом M байт. Если свободное пространство такого размера отсутствует, она может попытаться переместить какой-нибудь один из блоков, чтобы освободить непрерывный участок нужной длины. Требуется выбрать для перемещения блок наименьшей длины. Если таких вариантов несколько, следует выбрать блок с наименьшим начальным адресом.

Ограничения: 0 <= N <= 100000, 1 <= V <= 1073741824

Исходные данные

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

Результат

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

Пример