Kiteretsu goes to his Chemistry Lab to perform the perfect reaction.
In his lab, he found N reagents numbered 1 to N. The i^{th} reagent has two properties - A_{i} and B_{i}.

A reaction can be performed between the reagents i and j only if A_{i} ≤ j.
 
If a reaction is performed between reagents i and j, i \cdot j amount of heat is produced. Out of this, D \cdot (B_{i} \oplus B_{j}) is absorbed and the rest heat is released. Here, \oplus denotes the [bitwise XOR] operation.

More formally, in a reaction between reagents i and j, the heat released is given by:
H(i,j)= i \cdot j - D \cdot (B_{i} \oplus B_{j})

Find the maximum possible heat which can be released in a reaction.

Note: The input of this problem is large, so use fast input/output methods.

------ Input Format ------ 

- The first line will contain T - the number of test cases. Then the test cases follow.
- First line of each test case contains two integers N, D.
- Second line of each test case contains N integers A_{1}, A_{2}, \ldots, A_{N}. 
- Third line of each test case contains N integers B_{1}, B_{2}, \ldots, B_{N}

------ Output Format ------ 

For each test case, print a single line, a single integer denoting the maximum possible heat that can be released in a reaction.

------ Constraints ------ 

$1 ≤ T ≤ 10$
$2 ≤ N ≤ 10^{6}$
$1 ≤ D ≤ 2000$
$(i+1) ≤  A_{i} ≤ N$ $\forall$ $(1 ≤ i < N)$ 
$A_{N}=N+1$
$1 ≤ B_{i} ≤ N$
- Sum of $N$ over all test cases does not exceed $10^{6}$.

----- Sample Input 1 ------ 
2
5 2
2 4 5 5 6
1 3 2 2 5
2 3
2 3
1 2

----- Sample Output 1 ------ 
6
-7

----- explanation 1 ------ 
Test Case $1$: Let us choose $i = 2$ and $j = 4$. Since $A_{2} ≤ 4$, a reaction can take place.  
The heat released in this reaction is $2\cdot 4 - 2\cdot (3 \oplus 2) = 8-2 \cdot 1 = 6$. It can be proven that for no other reaction, the heat released is greater than $6$.  
Some other reactions can take place between $(2, 5)$, $(3,5)$. Note that no reaction is possible between $(3,4)$ as $A_{3} \nleq 4$.

Test Case $2$: The only possible reaction is between reagents $1$ and $2$. The heat released in this reaction is $1 \cdot 2 - 3\cdot (1 \oplus 2) = 2 - 3\cdot 3 = -7$.

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Mathematics

Complete search


Solutions:
t = int(input())
for _ in range(t):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	mx_heat = None
	for i in range(n - 1, 0, -1):
		if mx_heat is not None and i * (i + 1) <= mx_heat:
			break
		for j in range(i - 1, -1, -1):
			if mx_heat is not None and (i + 1) * (j + 1) <= mx_heat:
				break
			if a[i] <= j + 1:
				heat = (i + 1) * (j + 1) - d * (b[i] ^ b[j])
				if mx_heat is None:
					mx_heat = heat
				else:
					mx_heat = max(mx_heat, heat)
			elif a[j] <= i + 1:
				heat = (i + 1) * (j + 1) - d * (b[i] ^ b[j])
				if mx_heat is None:
					mx_heat = heat
				else:
					mx_heat = max(mx_heat, heat)
	print(mx_heat)