ЛШ 2007 - 4 - Выходные

Задача B. Выходные ≡

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

Автор:	Жюри всероссийских зимних сборов школьников 2007-2008	Ограничение времени:	2 сек
Входной файл:	holidays.in	Ограничение памяти:	64 Мб
Выходной файл:	holidays.out
Максимальный балл:	100

Условие

В огромной международной компании работает n программистов. Все программисты работают удаленно, а общаются только по телефону или ICQ. Проблема состоит в том, что все они живут в разных странах. В этих странах разные традиции и разные праздники. Компания уважает государственные праздники всех своих сотрудников, поэтому не может заставлять их выходить на работу в такие дни. Сейчас перед советом директоров фирмы стоит задача назначить одного из программистов руководителем проекта. Но если руководитель приходит на работу и не может связаться с одним из своих сотрудников (так как у него выходной), то он недоволен.

Если он не может связаться более, чем с k сотрудниками, то руководитель просто приходит в ярость. Скажем, что степень недовольства в некоторый рабочий день руководителя вычисляется как количество сотрудников, с которыми он не может связаться. Если руководитель приходит в ярость, то степень его недовольства в этот день равна 10 ⋅ k.

Совет директоров принял решение, что руководителем проекта нужно назначить человека, суммарная степень недовольства которого за все время работы будет минимальным. (Главное — моральное состояние сотрудников. Совершенно не важна квалификация руководителя). Несмотря на то, что в фирме огромное количество программистов высокого уровня, которые бы с легкостью справились с этой задачей, никому из них нельзя доверить ее решение, так как они заинтересованы стать руководителями проекта сами. Поэтому решение этой задачи поручается независимому эксперту, то есть Вам.

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

Во входном файле содержится два числа — n и k. Далее в n строках следует описание праздников каждого из программистов. Сначала записано количество государственных праздников p, а затем следует p пар чисел l и r, задающие непересекающиеся отрезки праздников в соответствующей стране. Обратите внимание, что, хотя отрезки, задающие праздники в одной стране, пересекаться не могут, в различных странах могут быть праздники в один и тот же день.

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

В выходной файл выведите ответ — номер программиста, которого нужно назначить руководителем. Программисты нумеруются с 1 в порядке их задания во входном файле. Если существует несколько вариантов, то выберите программиста с наименьшим номером. (Программисты записаны в порядке уменьшения их квалификации).

Ограничения

1 ≤ n, k ≤ 10⁵

0 ≤ p ≤ 10⁵

1 ≤ l ≤ r ≤ 10⁵

Суммарное количество отрезков не превосходит 10⁵.

Все числа во входном файле целые.

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

№	Входной файл (`holidays.in`)	Выходной файл (`holidays.out`)
1	`2 1 2 1 3 5 10 1 4 4`	`1`
2	`3 1 1 1 1 2 1 2 5 7 1 2 10`	`2`