Maximum utility

★★★★★

3.2

6 votes

Basic Programming, Bit Manipulation, Basics of Bit Manipulation, Algorithms, Greedy Algorithms, Bit manipulation

Details

Submissions

Discussion

Editorial

Problem

You are given an array $A$ containing $N$ integers. The $i^{th}$ integer is $A_i$ and has a utility of $B_i$ . You select a combination of integers whose bitwise OR is less than or equal to $K$ .

You are required to make the sum of utilities of selected integers to be as large as possible.

Input format

The first line contains an integer $T$ denoting the number of test cases.
The first line of each test case contains two space-separated integers $N$ and $K$ .
The second line of each test case contains $N$ space-separated integers denoting array $A$ .
The third line of each test case contains $N$ space-separated integers denoting array $B$ .

Output format

For each test case, print the maximum possible sum of utilities of selected integers in a new line.

Constraints

$1 \le T \le 1000\\ 1 \le N \le 200000\\ 0 \le K,A_i,B_i < 2^{30}$

It is guaranteed that the sum of $N$ over $T$ test cases does not exceed $1e6$ .

Sample Input

2
4 11
11 8 15 4
10 14 5 9
5 12
0 11 11 2 5
10 15 9 12 12

Sample Output

24
46

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

For the first testcase, we select $A_1$ and $A_2$ , therefore $A_1|A_2 = 11\le K$ , and the maximum sum of utilities is $10+14=24$ .

For the second testcase, we select $A_1, A_2, A_3$ and $A_5$ , therefore $A_1|A_2|A_3|A_5=11<K$ , and the maximum sum of utilities is $10+15+9+12=46$ .

Contributers:

Lokesh Singh

Arpa PoorAkhavan