题目描述

在数轴上，你的初始位置坐标为$\red{0，}$你有$\red{m}$枚硬币，以及$\red{n}$个移动的操作，每个移动操作花费的硬币数和移动距离分别为$\red{v_i}$和$\red{w_i}$。

在这个游戏中移动的规则是，当你选择了一个移动操作，你移动后的位置为你当前位置与该移动操作的移动距离的异或结果（即二进制不进位加法）。

是否存在选择移动操作的方法可以正好把你的硬币花完呢？如此移动完毕后你与初始位置的距离最大是多 少？

输入格式

第一行输入一个正整数$\red{T}$表示测试数据的组数；

第二行输入两个正整数$\red{n，}$$\red{m}$分别表示硬币的个数和操作的个数；

接下来$\red{n}$行，每行两个正整数$\red{v_i,w_i}$分别表示对应每个移动操作花费的硬币和移动距离。

输出格式

对于每一组测试数据，输出一个整数表示最终你与初始位置距离的最大值；

如果硬币不能被正好花费完，输出"$\red{-1}$".

样例

输入样例

1 
5 4 
2 4 
1 6 
2 2 
2 12 
1 14

输出样例

14

提示

对于$\red{100\%}$的数据，$\red{1<=T<=10,1<=n,m<=2^{10},1<=v_i,w_i<=2^{10}}$；

对于其中$\red{60\%}$的数据，$\red{1<=T<=10,1<=n,m<=100,1<=v_i,w_i<=100}$