Вы создаете уровень для некоторой мобильной игры. Уровень состоит из нескольких клеточек, выстроенных в ряд слева направо и пронумерованных последовательными натуральными числами, начиная с \(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\)?
Выходные данные
Для каждого тестового случая выведите одно целое число — минимальное количество секунд, необходимое вам, чтобы изменить уровень соответствующим образом.
Можно показать, что всегда возможно изменить уровень так, чтобы его можно было пройти.
Примечание
В первом тестовом случае лучше всего просто убрать первую клеточку, после чего все необходимые платформы будут на своих местах: 0101010101. Зачеркнутая цифра удалена, цифры, выделенные жирным — места, где должны быть платформы. Необходимое время равно \(y = 2\).
Во втором тестовом случае лучше всего добавить платформы в клетки \(4\) и \(5\): 00000 \(\to\) 00011. Необходимое время равно \(x \cdot 2 = 4\).
В третьем тестовом случае лучше всего удалить первую клеточку дважды и затем добавить платформу в клеточку, которая изначально была \(10\)-й: 10110011000 \(\to\) 10110011010. Необходимое время равно \(y \cdot 2 + x = 10\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
10 3 2
0101010101
2 2
5 4 1
00000
2 10
11 2 3
10110011000
4 3
|
2
4
10
|