暂无测试数据。

题目背景

小G 是个吃货，但是个吝啬的吃货。

对于一种食物（比如桃子啊，西瓜啊，大蒜啊～），小G 通常会对它们有两个定义：

• 一个是好吃指数 $a_i$；
• 一个是价钱 $b_i$。

如果要吃一个食物，自然要先买它，所以就要先付出代价。

而且 小G 的幸福指数计算方式非常奇怪，如果说吃的东西的异或和为 $A$，那么把这个 $A$ 转成二进制的数之后，如果第 $i$ 位（二进制最低位为第 $0$ 位）上为 $1$，那么就会增加 $c_i$ 的幸福值。

小G 想让幸福值减去总花费最大，你能帮帮它么？只需要告诉 小G 这个最大值是多少即可。

题目描述

有 $n$ 个物品，每个物品两种属性 $a_i,b_i$。可以从中选出若干物品，其代价为 $\sum b_i$。

对于选出来的数，设 $A=\oplus a_i$，那么对于 $A$ 二进制数中，若第 $i$ 位为 $1$，则有 $c_i$ 的收益。

注：这里的 $\oplus$ 指的是连续异或和。

求哪种选择物品的方案使得收益减代价的最大，输出最大的结果。可以不选。

输入格式

第一行两个整数 $n,m$，$n$ 表示物品个数，$m$ 表示数据的大小范围，具体含义参考数据范围。

接下来 $n$ 行，每行两个整数 $a_i$ 和 $b_i$，含义如上所示。

接下来一行 $m$ 个数，第 $i$ 个数表示 $c_{i-1}$。

输出格式

一行，表示最大收益。

数据范围

对于 $20\%$ 的数据：$n\le 8,m\le 5$；

对于 $40\%$ 的数据：$n\le 200$；

另有 $10\%$ 的数据：$m=2$；

对于 $100\%$ 的数据：$1\le n\le 10^4,1\le m\le 15,0\le a_i< 2^m,1\le b_i,c_i\le 10^9$。

5 4
0 10
14 8
3 3
1 7
14 7
8 10 4 4

15

4 2
3 10
1 8
2 5
2 3
6 2

0