Однажды на
факультативе по математике Вася научился играть в одну интересную
математическую игру. Имеется набор фишек, на каждой фишке написана её
стоимость. Вначале игроку выдаётся какая-то из фишек из этого набора (ходом это
не считается). Далее на каждом ходе игрок может забрать себе любую фишку из
оставшихся при условии, что её стоимость меньше суммарной стоимости уже
имеющихся у него фишек. Цель игры – забрать фишку с максимальной стоимостью,
сделав для этого наименьшее число ходов.
Во время игры
Вася столкнулся с такой проблемой: чтобы узнать, выиграл он или нет, нужно
проверить, действительно ли было сделано минимально возможное число ходов.
Напишите программу, которая ему в этом поможет.
В первой
строке входных данных записано целое число 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
|
Примечание: набор тестов расширен по сравнению с теми, что были на олимпиаде (спасибо Олегу Стрекаловскому).
