← 返回题目列表

Codeforces · 1456/E

E. XOR 范围

中文机器翻译题面 查看原题

给定整数 $$$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 的位上的总和。

让我们定义长度为 $$$n \ge 2$$$ 的数组 $$$a$$$ 的成本,其元素来自 $$$[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}$$$)。

输出

输出一个整数——满足所有限制的数组的最小成本。

示例

输入 #1

4 3
3 3
5 5
6 6
1 1
5 2 7

输出 #1

30

输入 #2

3 3
2 2
3 4
4 6
1 10 100

输出 #2

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]$$$。