All submissions for this problem are available.
Please refer to sample test in English version of statement.
Except for that, you can read problem statement in Mandarin Chinese, Russian and Vietnamese.
There are N ice-creams placed in a row in a shop, where the i-th has cost C[i] and flavor F[i]. Chef wants to buy some consecutive segment of ice-creams so that their total cost doesn't exceed his budget K, and he can mix some subset of bought ice-creams to make a new ice-cream with maximum possible flavor.
Mixing m ice-creams of flavors A1, A2, .., Am will result in an ice-cream of flavor equal to A1 ^ A2 ^ ... ^ Am where ^ is the xor operation.
What is maximum possible flavor that Chef can get? It's guaranteed that at least one ice-cream has cost that doesn't exceed Chef's budget.
First line contains an integer T, which is the number of test-cases.
The first line of each test-case contains two integers: N and K.
Each of the following N lines contains two integers C[i] and F[i].
Output the answer of each test-case in new line, the maximum flavor that the Chef can get.
- 1 ≤ T ≤ 10,000
- 1 ≤ N ≤ 100,000
- sum of N in all test-cases will not exceed 100,000
- 1 ≤ K ≤ 10^14
- 1 ≤ F[i] ≤ 10^9
- 1 ≤ C[i] ≤ 10^9
- C[i] ≤ K for at least one i
Input: 2 5 15 2 4 7 1 5 9 15 6 3 12 3 1000 123 8 99999 1 80 7 Output: 13 8
Test case 1: The binary representations of the 5 flavors, in order, are: (0100, 0001, 1001, 0110, 1100), and the corresponding prices are (2,7,5,15,3).
If Chef buys only the 5th ice-cream with cost 3 and flavor 12. But if Chef buys the first 3 ice-creams, his total cost is 2+7+5 = 14, which is within his budget of 15, and hence valid. Now, from these three bought ice-creams, he can choose to mix just the first and third, and get a flavor of 0100^1001 = 1101, which is 13. You can verify that this is the best that he can do.
Test case 2: Chef can afford the first or the last ice-cream. He could afford them both but he must buy a consecutive segment of ice-creams while the cost of the second ice-cream is beyond his budget.
It's optimal to buy the first ice-cream only and use its flavor only, what gives us the answer 8.
|Tags||cook79, gauss-elim, kingofnumbers, medium-hard, two-pointers|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.