E. XOR-интервалы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны целые числа $$$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}$$$.

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

В первой строке находятся два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 50$$$, $$$1 \le k \le 50$$$) — длина массива и битовая длина рассматриваемых чисел.

В следующих $$$n$$$ строках перечислены ограничения на элементы массива: в $$$i$$$-й строке находятся целые числа $$$l_{i}$$$ и $$$r_{i}$$$ ($$$0 \le l_{i} \le r_{i} < 2^{k}$$$).

В последней строке находятся целые числа $$$c_{0}, c_{1}, \ldots, c_{k-1}$$$ ($$$0 \le c_{i} \le 10^{12}$$$).

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

Выведите одно целое число — минимальную стоимость массива, удовлетворяющего всем ограничениям.

Примеры
Входные данные
4 3
3 3
5 5
6 6
1 1
5 2 7
Выходные данные
30
Входные данные
3 3
2 2
3 4
4 6
1 10 100
Выходные данные
102
Примечание

В первом примере есть только один подходящий массив — $$$[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]$$$.