Backpack
Time Limit : 3000/1500ms (Java/Other) Memory Limit : 65536/65536K (Java/Other)
Total Submission(s) : 0 Accepted Submission(s) : 0
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
Alice has a backpack of capacity $m$ that she now wants to fill with some items!
Alice has $n$ items, each of which has a volume $v_i$ and a value $w_i$.
Can a number of items be selected from n items such that the backpack is exactly full (ie the sum of the volumes equals the backpack capacity)? If so, what is the maximum XOR sum of the values of the items in the backpack when the backpack is full?
Alice has $n$ items, each of which has a volume $v_i$ and a value $w_i$.
Can a number of items be selected from n items such that the backpack is exactly full (ie the sum of the volumes equals the backpack capacity)? If so, what is the maximum XOR sum of the values of the items in the backpack when the backpack is full?
Input
The first line contains an integer $T(T \le 10)$ —the number of test cases.
The first line of each test case contains 2 integers $n,m(1 \le n,m < 2^{10})$ —the number of items, the capacity of the backpack.
The next $n$ lines , each line contains 2 integers $v_i,w_i(1 \le v_i,w_i < 2^{10})$ — the volume and value of the item.
The first line of each test case contains 2 integers $n,m(1 \le n,m < 2^{10})$ —the number of items, the capacity of the backpack.
The next $n$ lines , each line contains 2 integers $v_i,w_i(1 \le v_i,w_i < 2^{10})$ — the volume and value of the item.
Output
For each test case, output a single line, if the backpack cannot be filled, just output a line of "-1", otherwise output the largest XOR sum.
Sample Input
1 5 4 2 4 1 6 2 2 2 12 1 14
Sample Output
14
Source
2022“杭电杯”中国大学生算法设计超级联赛（1）