B. Митинг
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

В столице Берляндии городе Берляндске проходят митинги против недавно прошедших выборов Царя Берляндии. Берляндская оппозиция под предводительством мистера Овального считает, что выборы были недостаточно честными и хочет организовать митинг на одной из площадей.

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

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

  • Оппозиция подает заявку на проведение митинга на одной из еще не занятых мэрией площадей.
  • Мэрия пытается перенести митинг на худшую площадь из еще не занятых. Для этого мэрия оплачивает проведение долгосрочного мероприятия на той площади, которая указана в заявке оппозиции, то есть занимает эту площадь, и предлагает оппозиции перенести митинг на худшую из незанятых площадей. Если оппозиция подала заявку на худшую площадь из незанятых, то мэрия не организует там свое мероприятие и заявка оппозиции принимается. Если у мэрии не хватает денег на проведение мероприятия на соответствующей площади, то все деньги мэрии тратятся, а мероприятие не проводится. В таком случае заявка считается принятой.
  • Если заявка не принята, то оппозиция может согласиться на предложение мэрии (то есть на худшую из незанятых площадей) или отозвать текущую заявку и попробовать подать другую на следующий день. Если дней до митинга не осталось, оппозиции ничего не остается, как согласиться на предложение мэрии. Если заявка принята, оппозиция также может отозвать текущую заявку и попробовать подать другую на следующий день. В этом случае площадь остается свободной.

Для того, чтобы организовать свое мероприятие на площади i, мэрии нужно потратить ai бурлей. Из-за кризиса у мэрии есть всего лишь b бурлей, чтобы противостоять оппозиции. Какую лучшую площадь может занять оппозиция, если мэрия каждый раз будет пытаться занимать площадь, на которую оппозиция подала заявку? Обратите внимание, действия мэрии всегда зависят только от действий оппозиции.

Входные данные

В первой строке записаны два целых числа n и k — количество площадей и дней до митинга соответственно (1 ≤ k < n ≤ 105).

Во второй строке записано целое число b — количество бурлей у мэрии (1 ≤ b ≤ 1018).

В третьей строке записано n целых чисел ai, разделенных пробелами, — количество денег, необходимых для проведения мероприятия на площади i (1 ≤ ai ≤ 109).

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++, вместо него рекомендуется использовать потоки cin, cout, а также спецификатор %I64d.

Выходные данные

Выведите одно число — минимальный номер площади, на которой сможет провести митинг оппозиция.

Примеры
Входные данные
5 2
8
2 4 5 3 1
Выходные данные
2
Входные данные
5 2
8
3 2 4 1 5
Выходные данные
5
Входные данные
5 4
1000000000000000
5 4 3 2 1
Выходные данные
5
Примечание

В первом примере оппозиция может действовать следующим образом. В первый день она займет площадь номер 3. Мэрия будет вынуждена организовать там мероприятие, после чего у нее останется 3 бурля. Если на второй день оппозиция подаст заявку на вторую площадь, то у мэрии не хватит денег, чтобы ее туда не пустить.

Во втором примере у оппозиции есть шансы только на последнюю площадь. Если первым ходом она занимают одну из первых четырех площадей, то у мэрии остается как минимум 4 бурля, и следующим ходом у нее хватит денег, чтобы перенести заявку с любой площади на последнюю.

В третьем примере у мэрии очень много денег, так что оппозиция может занять только последнюю площадь.