Однажды на факультативе по математике Вася научился играть в одну интересную математическую игру. Имеется набор фишек, на каждой фишке написана её стоимость. Вначале игроку выдаётся какая-то из фишек из этого набора (ходом это не считается). Далее на каждом ходе игрок может забрать себе любую фишку из оставшихся при условии, что её стоимость меньше суммарной стоимости уже имеющихся у него фишек. Цель игры – забрать фишку с максимальной стоимостью, сделав для этого наименьшее число ходов.

Во время игры Вася столкнулся с такой проблемой: чтобы узнать, выиграл он или нет, нужно проверить, действительно ли было сделано минимально возможное число ходов. Напишите программу, которая ему в этом поможет.

В первой строке входных данных записано целое число N – количество фишек  (2 ≤ N ≤ 30000).  В следующей строке через пробел записаны N целых чисел С_i – стоимости фишек (1 ≤ С_i ≤ 10 000). В третьей строке записан номер фишки M, которую выдали игроку (1 ≤ M ≤ N).

Выведите одно число K – минимальное количество ходов, за которое можно забрать фишку с максимальной стоимостью. Если выиграть невозможно, выведите -1. Если же фишка с максимальной стоимостью сразу была выдана игроку, выведите 0.

 

Пример ввода 1 5 20 50 40 100 50 2 Пример вывода 1 3

Пример ввода 2 5 20 50 40 100 50 1 Пример вывода 2 -1

Пример ввода 3 2 20 10 1 Пример вывода 2 0

 

Примечание: набор тестов расширен по сравнению с теми, что были на олимпиаде (спасибо Олегу Стрекаловскому).