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

Дима работает на складе чисел. Он входит на склад с двоичным числом $$$x=0$$$. Ему необходимо превратить свое число $$$x$$$ в число $$$s$$$. Для этого на складе есть два автомата для увеличения чисел.

Первый автомат увеличивает двоичное число $$$x$$$ на $$$1$$$ за $$$a$$$ секунд. Он расположен слева от входа на склад, в $$$p$$$ секундах ходьбы от входа.

Второй автомат умножает двоичное число $$$x$$$ на $$$2$$$ за $$$b$$$ секунд. Он расположен справа от входа на склад, в $$$q$$$ секундах ходьбы от входа.

Таким образом, если Диме понадобится дойти от одного автомата до другого, он потратит $$$p+q$$$ секунд. Исходно он находится у входа на склад.

Помогите Диме узнать, за какое наименьшее количество секунд можно получить число $$$x=s$$$ и вернуться ко входу на склад.

Число в двоичной системе счисления из $$$n$$$ цифр, представимое в виде: $$$\overline{a_1 a_2 \ldots a_n}$$$ $$$(a_i \in \{0, 1\})$$$, равно $$$2^{n-1} \cdot a_1 + 2^{n-2} \cdot a_2 + \ldots + 2 \cdot a_{n-1} + a_n$$$. ($$$a_1 = 1$$$ при $$$n > 1$$$, то есть число не имеет ведущих нулей).

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

В первой строке даны два целых числа $$$a$$$ и $$$b$$$ в десятичной записи $$$(1 \le a, b \le 10^9)$$$ — время, которое потребуется автоматам для увеличения числа.

Во второй строке даны целые числа $$$p$$$ и $$$q$$$ в десятичной записи $$$(0 \le p, q \le 10^9)$$$ — расстояние от входа на склад до первого и второго автоматов.

В третьей строке дано число $$$s$$$ в двоичной системе счисления без ведущих нулей (кроме случая $$$s = 0$$$). Длина числа $$$s$$$ не превышает $$$100\,000$$$ цифр.

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

Выведите минимальное количество секунд, которое потребуется, чтобы из $$$x=0$$$ получить $$$x=s$$$, пользуясь автоматами, и вернуться ко входу на склад.

Система оценки

Задача состоит из 25 тестов, не считая тестов из условия. Каждый тест оценивается независимо в 4 балла. Все тесты можно разделить на следующие группы:

НомерМакс. баллДоп. ограничения
$$$1$$$$$$20$$$Размер $$$s$$$ не больше 5
$$$2$$$$$$20$$$Размер $$$s$$$ не больше 20
$$$3$$$$$$20$$$$$$p=q=0$$$
$$$4$$$$$$20$$$Размер $$$s$$$ не больше $$$1000$$$
$$$5$$$$$$20$$$Размер $$$s$$$ не больше $$$100\,000$$$

Примеры

Входные данные
1 2
2 3
101011
Выходные данные
28
Входные данные
10 20
30 40
0
Выходные данные
0

Примечание

В первом тесте необходимо получить число $$$s=32 + 8 + 2 + 1 = 43$$$ в десятичной записи.

Оптимальная последовательность действий: Дима идет к первому автомату (2 секунды), прибавляет к числу единицу 5 раз (5 секунд), потом идет ко второму автомату ($$$2+3=5$$$ секунд), умножает число 3 раза ($$$3 \cdot 2 = 6$$$ секунд) и получает число 40, возвращается к первому автомату ($$$3+2=5$$$ секунд), прибавляет единицу 3 раза (3 секунды), и идет ко входу на склад (2 секунды). Всего потрачено 28 секунд.

Во втором тесте у Димы с самого начала есть число $$$x=0$$$.