#2711. 移动

移动

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

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

输入格式

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

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

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

输出格式

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

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

样例

输入样例

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

输出样例

14

提示

对于100%\red{100\%}的数据,1<=T<=10,1<=n,m<=210,1<=vi,wi<=210\red{1<=T<=10,1<=n,m<=2^{10},1<=v_i,w_i<=2^{10}}

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

普及组测试5

未参加
状态
已结束
规则
IOI
题目
4
开始于
2022-8-13 18:00
结束于
2022-8-13 21:00
持续时间
3 小时
主持人
参赛人数
46