You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有 $n$ 个物品，每个物品价格 $A_i$ ，收益为 $B_i$ ，由于一些奥妙重重的原因，当你买了一些物品，总价格为选择的 $A_i$ 的按位或而不是代数相加！

你身上只有 $k$ 元钱，你希望选择总价格不超过 $k$ 的一些物品，来获得最大的收益。

输入格式

第一行两个整数 $n,k$。

接下来 $n$ 行，每行两个整数 $A_i,B_i$，意义见题目描述。

输出格式

一行一个整数，表示答案。

样例输入

3 7
5 10
6 100
8 1000

样例输出

110

数据范围

对于$30\%$的数据，$k < 2^{10}$

对于另外$30\%$的数据，$n\leq 21$

对于所有数据，$1\leq n\leq 10^5,0\leq k < 2^{30},0\leq A_i < 2^{30},0\leq B_i \leq 10^9$