小田的01背包

题目描述

小田有一个容量为 $k$ 的背包，现在有 $n$ 个物品，每个物品有一个体积 $v$ 和 价值 $w$，他想知道在体积不超过 $k$ 的前提下，他最多能装价值为多少的物品。

在本问题中，物品的总体积定义为所装物品的体积的 $\&$ (按位与)，总价值也定义为所装物品的价值的 $\&$ (按位与)。如果不选物品，则价值为 $0$，所占体积也为 $0$ 。

输入描述

输入包含 $n+1$ 行。

第一行两个正整数 $n,k$，表示物品个数和背包容量。

接下来 $n$ 行，每行两个正整数 $v_{i} \;, w_{i}$，表示每个物品的体积和价值。

输出描述

输出包含一行一个整数，表示能装的最大价值

输入输出样例

输入 #1

3 1
7 3
10 7
9 6

输出 #1

2

输入 #2

5 5
10 6
8 9
7 4
6 6
3 1

输出 #2

6

说明/提示

【样例 1 解释】

选第一个物品和第三个物品。

体积为：$7 \& 9 = 1$。

价值为：$3 \& 6 = 2$。

另一个方案是三个物品全选。

体积为：$7 \& 9 \& 10 = 0$。

价值为：$3 \& 6 \& 7 = 2$。

【数据范围】

对于 $10 \%$ 的数据，保证所有 $v_i$ 都小于等于 $k$。

对于所有测试数据，有：$1 \le n \le 1 \times 10^{3}, 1 \le k \le 4 \times 10^{4}, 1 \le v_{i} \; , w_{i} \le 4 \times 10^{4}$ 。