B. Цикл
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Боб любит играть в интересную игру в жанре tower defense на своем мобильном телефоне. В игре он должен разыгрывать карты, чтобы победить своих противников!

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

Одна карта называется картой условия победы, и Боб хочет разыграть её как можно больше раз. Однако каждая карта также имеет стоимость, необходимую для розыгрыша. $$$i$$$-я карта (изначально расположенная на $$$i$$$-й позиции) стоит Бобу $$$a_i$$$ энергии каждый раз, когда она разыгрывается. Общая стоимость разыгранных карт не должна превышать $$$m$$$. Изначально карта условия победы находится на $$$p$$$-й позиции в очереди.

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

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит четыре целых числа $$$n,k,p,m$$$ ($$$1\le k,p\le n\le 5000$$$, $$$1\le m\le 5000$$$), обозначающих количество карт, количество карт которые можно разыграть в каждый момент времени, начальную позицию карты условия победы и общую доступную энергию.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le m$$$), обозначающих стоимость каждой карты.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5000$$$.

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

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

Пример
Входные данные
4
2 1 2 42
42 1
3 3 2 6
2 1 2
3 2 2 6
2 1 2
8 4 7 10
3 4 4 2 1 1 4 2
Выходные данные
0
6
2
1
Примечание

В первом наборе входных данных мы можем разыграть только первую карту в колоде, и её розыгрыш использует всю энергию. Поскольку карта условия победы является второй картой, мы не можем разыграть её, пока энергия не иссякнет. Поэтому ответ равен $$$0$$$.

Во втором наборе входных данных мы можем разыграть все карты в колоде. Оптимальная стратегия, очевидно, заключается в том, чтобы разыгрывать только карту условия победы. Поскольку её стоимость составляет $$$1$$$ энергию, а у нас всего $$$6$$$ энергии, мы можем разыграть её $$$6$$$ раз, прежде чем энергия иссякнет. Поэтому ответ равен $$$6$$$.

В третьем наборе входных данных мы можем разыгрывать карты следующим образом: (карта условия победы выделена красным)

Начальная колода: $$$[2,\color{red}{1},2]$$$.

Разыгрываем первую карту: колода становится $$$[\color{red}{1},2,2]$$$.

Разыгрываем первую карту снова: колода становится $$$[2,2,\color{red}{1}]$$$.

Разыгрываем первую карту ещё раз: колода становится $$$[2,\color{red}{1},2]$$$.

Разыгрываем вторую карту: колода становится $$$[2,2,\color{red}{1}]$$$.

В процессе мы разыграли карту условия победы $$$2$$$ раза, и мы использовали $$$6$$$ энергии в общей сложности. Можно показать, что никакая стратегия не позволяет нам разыграть карту условия победы более $$$2$$$ раз, не превышая $$$6$$$ очков энергии; поэтому ответ равен $$$2$$$.

В четвертом наборе входных данных можно показать, что мы можем разыграть карту условия победы не более одного раза. Это достигается, если всегда разыгрывать $$$4$$$-ю карту в колоде. Поэтому ответ равен $$$1$$$.