Дима работает на складе чисел. Он входит на склад с двоичным числом \(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\), пользуясь автоматами, и вернуться ко входу на склад.
Примечание
В первом тесте необходимо получить число \(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\).