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

Вы создаете уровень для некоторой мобильной игры. Уровень состоит из нескольких клеточек, выстроенных в ряд слева направо и пронумерованных последовательными натуральными числами, начиная с $$$1$$$. Каждую клеточку вы можете оставить пустой или расположить там платформу.

Чтобы пройти уровень, игрок должен бросить мяч слева так, чтобы он сначала упал на платформу в некоторой клеточке $$$p$$$, отскочил от нее, затем отскочил от платформы в клеточке $$$(p + k)$$$, затем от платформы в клеточке $$$(p + 2k)$$$, и так далее от платформы в каждой $$$k$$$-й клеточке до тех пор, пока он не перепрыгнет правее последней клеточки. Если хотя бы одна из этих клеточек не содержит платформы, то уровень с такими значениями $$$p$$$ и $$$k$$$ пройти нельзя.

У вас уже есть некоторый шаблон уровня, описываемый числами $$$a_1$$$, $$$a_2$$$, $$$a_3$$$, ..., $$$a_n$$$, где $$$a_i = 0$$$ означает, что в клеточке $$$i$$$ нет платформы, а $$$a_i = 1$$$ означает, что платформа там есть. Вы хотите модифицировать этот шаблон так, чтобы уровень можно было пройти с заданными $$$p$$$ и $$$k$$$. За $$$x$$$ секунд вы можете добавить платформу в любую пустую клеточку. За $$$y$$$ секунд вы можете полностью убрать первую клеточку, при этом количество клеточек уменьшится на один, а оставшиеся клетки пронумеруются заново, сохраняя порядок. Других изменений вы вносить не можете. Вы не можете уменьшить число клеток до меньше $$$p$$$.

Иллюстрация к третьему тестовому случаю. Крестами отмечены удаленные клеточки. Синим показана добавленная платформа.

Какое минимальное количество секунд вам требуется, чтобы сделать возможным прохождение уровня с заданными значениями $$$p$$$ и $$$k$$$?

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

Первая строка содержит количество тестовых случаев $$$t$$$ ($$$1 \le t \le 100$$$). Далее следуют описания тестовых случаев.

Первая строка каждого тестового случая содержит три целых числа $$$n$$$, $$$p$$$ и $$$k$$$ ($$$1 \le p \le n \le 10^5$$$, $$$1 \le k \le n$$$) — начальное количество клеточек, номер первой клеточки, которая должна содержать платформу, и требуемый период прыжков мяча.

Вторая строка каждого тестового случая содержит строку $$$a_1 a_2 a_3 \ldots a_n$$$ ($$$a_i = 0$$$ или $$$a_i = 1$$$) — начальный шаблон уровня, записанный без пробелов.

Последняя строка каждого тестового случая содержит два целых числа $$$x$$$ и $$$y$$$ ($$$1 \le x, y \le 10^4$$$) — время, необходимое для добавления платформы и время, необходимое для удаления первой клеточки, соответственно.

Сумма $$$n$$$ по всем тестовым случаям не превосходит $$$10^5$$$.

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

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

Можно показать, что всегда возможно изменить уровень так, чтобы его можно было пройти.

Пример
Входные данные
3
10 3 2
0101010101
2 2
5 4 1
00000
2 10
11 2 3
10110011000
4 3
Выходные данные
2
4
10
Примечание

В первом тестовом случае лучше всего просто убрать первую клеточку, после чего все необходимые платформы будут на своих местах: 0101010101. Зачеркнутая цифра удалена, цифры, выделенные жирным — места, где должны быть платформы. Необходимое время равно $$$y = 2$$$.

Во втором тестовом случае лучше всего добавить платформы в клетки $$$4$$$ и $$$5$$$: 00000 $$$\to$$$ 00011. Необходимое время равно $$$x \cdot 2 = 4$$$.

В третьем тестовом случае лучше всего удалить первую клеточку дважды и затем добавить платформу в клеточку, которая изначально была $$$10$$$-й: 10110011000 $$$\to$$$ 10110011010. Необходимое время равно $$$y \cdot 2 + x = 10$$$.