永雏塔菲的背包
题号:NC244094
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

永雏塔菲有一个容量为m的背包,小塔菲想往包包里装一些物品喵。
现在有n个物品,每个物品的体积为v_i,价值为w_i。小塔菲想从n个物品中选择一些物品来完全装满背包(即体积之和等于背包容量),如果可以装满的话,当背包装满时,背包中物品的值的最大异或和是多少?

输入描述:

第一行输入一个 T,表示有T(T\le 10)个测试用例。
对于每个测试用例:
第一行包含 2 个整数 n, m(1 \le n, m < 210),分别代表物品数量和背包容量;
接下来 n 行,每行包含 2 个整数 v_i, w_i(1 \le v_i, w_i < 210),分别表示物品的体积和价值

输出描述:

对每个测试用例,输出一行:

如果背包不能填满,则输出一行1;

否则输出最大的异或和。

示例1

输入

复制
1
5 4
2 4
1 6
2 2
2 12
1 14

输出

复制
14