Даны целые числа \(c_{0}, c_{1}, \ldots, c_{k-1}\). Определим цену числа \(0 \le x < 2^{k}\) как \(p(x) = \sum_{i=0}^{k-1} \left( \left\lfloor \frac{x}{2^{i}} \right\rfloor \bmod 2 \right) \cdot c_{i}\). Иными словами, цена числа \(x\) — это сумма \(c_{i}\) по тем битам \(x\), которые равны 1.
Определим стоимость массива \(a\) длины \(n \ge 2\), состоящего из целых чисел из полуинтервала \([0, 2^{k})\) следующим образом: \(cost(a) = \sum_{i=1}^{n - 1} p(a_{i} \oplus a_{i+1})\), где \(\oplus\) обозначает операцию побитового исключающего ИЛИ.
Вам нужно построить массив длины \(n\) минимальной стоимости, в котором каждый элемент должен принадлежать определенному отрезку: \(l_{i} \le a_{i} \le r_{i}\).
Выходные данные
Выведите одно целое число — минимальную стоимость массива, удовлетворяющего всем ограничениям.
Примечание
В первом примере есть только один подходящий массив — \([3, 5, 6, 1]\), — и его стоимость равна \(cost([3, 5, 6, 1]) = p(3 \oplus 5) + p(5 \oplus 6) + p(6 \oplus 1) = p(6) + p(3) + p(7) = (c_{1} + c_{2}) + (c_{0} + c_{1}) + (c_{0} + c_{1} + c_{2}) = (2 + 7) + (5 + 2) + (5 + 2 + 7) = 30\).
Во втором примере единственный оптимальный массив — \([2, 3, 6]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
3 3
5 5
6 6
1 1
5 2 7
|
30
|
|
2
|
3 3
2 2
3 4
4 6
1 10 100
|
102
|