Танос хочет уничтожить базу мстителей вместе с мстителями, которые там находятся.
Представим базу как массив, в каждой ячейке которой может находиться сколько угодно мстителей, но каждый мститель находится ровно в одной ячейке. Длина базы является точной степенью \(2\). Танос хочет уничтожить базу, потратив минимум энергии. Он начинает со всей базы и за один шаг может сделать одно из следующего:
- если текущая длина базы хотя бы \(2\), разделить базу на \(2\) равные половины и продолжить их уничтожать независимо, или
- сжечь текущую базу. Если на ней нет мстителей, это отнимает \(A\) единиц энергии, иначе это отнимает \(B \cdot n_a \cdot l\) единиц энергии, где \(n_a\) — число мстителей на этой базе, а \(l\) — длина текущей базы.
Выведите минимальное число единиц энергии, которое должен затратить Танос, чтобы уничтожить всю базу.
Выходные данные
Выведите одно целое число — минимальное число единиц энергии, которое должен затратить Танос, чтобы уничтожить базу.
Примечание
Рассмотрим первый пример.
Один из вариантов для Таноса — сжечь базу \(1-4\) целиком, затратив \(2 \cdot 2 \cdot 4 = 16\) единиц энергии.
В другом варианте он может разделить базу на две части \(1-2\) и \(3-4\).
Для базы \(1-2\) он может либо сжечь ее целиком, затратив \(2 \cdot 1 \cdot 2 = 4\) единиц энергии, либо разделить ее на \(2\) части \(1-1\) и \(2-2\).
Для базы \(1-1\) он может сжечь ее, затратив \(2 \cdot 1 \cdot 1 = 2\) единиц энергии. Для базы \(2-2\), он может сжечь ее, затратив \(1\) единицу энергии, так как на ней нет мстителей. Поэтому он может уничтожить базу \(1-2\) за \(2 + 1 = 3\) единицы энергии, что меньше, чем \(4\).
Аналогично, необходимо \(3\) единицы энергии, чтобы уничтожить \(3-4\). Итого, можно уничтожить всю базу за \(6\) единиц энергии.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2 1 2
1 3
|
6
|
|
2
|
3 2 1 2
1 7
|
8
|