Ограниченное прогнозирование места
Думаете, выиграть соревнование легко? Это не тот случай, если вокруг так много легендарных конкурентов.
Вы принимаете участие в соревновании по программированию OpenBowl. Оно состоит из двух раундов - онлайн и онсайт раундов. Кроме Вас еще имеется n - 1 участник, каждый из которых хочет победить. Каждый из n участников уже принял участие в онлайн раунде, на нем участник i получил в точности a_i балов (у Вас нет даже идеи как эти числа были подсчитаны - только Sn., главный организатор соревнования знает об этом все; Вы только слышали что это как-то связано с условно нерейтинговыми раундами).
Наконец наступило время онсайт раунда. На онсайт раунде каждый из участников занимает некоторое место между 1 и n включительно, и никакие два участника не занимают одно место. За место j на онсайт раунде дается p_j балов. Окончательное количество балов для каждого участника равно сумме балов набранных на онлайн и онсайт раундах. Затем подсчитывается финальное место каждого участника - для участника i оно равно k + 1, где k - число участников, чьё финальное количество балов строго больше чем у i-го участника.
Вы четко понимаете, что Ваши соперники очень сильны. Вот почему Вы даже не нацелены на победу в конкурсе. Вы решили, что будете довольны своим результатом, если займете итоговое место не ниже x. Теперь Вы хотели бы узнать: какое самое низкое место достаточно занять в онсайт раунде, чтобы гарантировать выше желаемое?
Входные данные
Первая строка содержит два целых числа n и x (1 ≤ x ≤ n ≤ 10^5), за которыми следуют n целых чисел a_i - количество балов, полученных i-ым участником во время онлайн раунда. Далее следуют n целых чисел p_j - количество балов, полученных участником, занявшим j-ое место участником во время онсайт раунда (0 ≤ a_i, p_j ≤ 10^9). Гарантируется, что p_j ≥ p_{j+1} для любого j (1 ≤ j < n). Вы - участник с номером 1.
Выходные данные
Вывести одно число между 1 и n включительно - самое низкое место на онсайт раунде, которое Вам достаточно занять чтобы гарантировать себе в общем зачете место x или выше, или -1 если этого гарантировать невозможно, даже если Вы выиграете онсайт раунд.