Məsələlər
Handicapped Onsite Prediction
Handicapped Onsite Prediction
Думаете, выиграть соревнование легко? Это не тот случай, если вокруг так много легендарных конкурентов.
Вы принимаете участие в соревновании по программированию OpenBowl. Оно состоит из двух раундов - онлайн и онсайт раундов. Кроме Вас еще имеется \textbf{n }- \textbf{1 }участник, каждый из которых хочет победить. Каждый из \textbf{n }участников уже принял участие в онлайн раунде, на нем участник \textbf{i }получил в точности \textbf{a_i} балов (у Вас нет даже идеи как эти числа были подсчитаны - только Sn., главный организатор соревнования знает об этом все; Вы только слышали что это как-то связано с условно нерейтинговыми раундами).
Наконец наступило время онсайт раунда. На онсайт раунде каждый из участников занимает некоторое место между \textbf{1 }и \textbf{n }включительно, и никакие два участника не занимают одно место. За место \textbf{j }на онсайт раунде дается \textbf{P_j} балов. Окончательное количество балов для каждого участника равно сумме балов набранных на онлайн и онсайт раундах. Затем подсчитывается финальное место каждого участника - для участника \textbf{i }оно равно \textbf{k} + \textbf{1}, где \textbf{k }- число участников, чьё финальное количество балов строго больше чем у i-го участника.
Вы четко понимаете, что Ваши соперники очень сильны. Вот почему Вы даже не нацелены на победу в конкурсе. Вы решили, что будете довольны своим результатом, если займете итоговое место не ниже \textbf{x}. Теперь Вы хотели бы узнать: какое самое низкое место достаточно занять в онсайт раунде, чтобы гарантировать выше желаемое?
\InputFile
Первая строка содержит два целых числа \textbf{n }и \textbf{x }(\textbf{1 }≤ \textbf{x }≤ \textbf{n }≤ \textbf{10^5}), за которыми следуют \textbf{n }целых чисел \textbf{a_i} - количество балов, полученных \textbf{i}-ым участником во время онлайн раунда. Далее следуют \textbf{n }целых чисел \textbf{p_j} - количество балов, полученных участником, занявшим \textbf{j}-ое место участником во время онсайт раунда (\textbf{0 }≤ \textbf{a_i}, \textbf{p_j} ≤ \textbf{10^9}). Гарантируется, что \textbf{p_j} ≥ \textbf{p_\{j+1\}} для любого \textbf{j} (\textbf{1 }≤ \textbf{j }< \textbf{n}). Вы - участник с номером \textbf{1}.
\OutputFile
Вывести одно число между \textbf{1 }и \textbf{n }включительно - самое низкое место на онсайт раунде, которое Вам достаточно занять чтобы гарантировать себе в общем зачете место \textbf{x }или выше, или \textbf{-1 }если этого гарантировать невозможно, даже если Вы выиграете онсайт раунд.
Giriş verilənləri #1
5 3 230 310 200 260 180 100 80 60 50 45
Çıxış verilənləri #1
2