Cobb

题意翻译

给定一个长度为 $n$ 的非负整数序列 $a_1,a_2\dots a_n$ 和一个正整数 $k$，求出 $\max(i\cdot j-k\cdot(a_i\texttt{ or } a_j))$ 。其中 $1\leq i <j\leq n$。

题目描述

You are given $ n $ integers $ a_1, a_2, \ldots, a_n $ and an integer $ k $ . Find the maximum value of $ i \cdot j - k \cdot (a_i | a_j) $ over all pairs $ (i, j) $ of integers with $ 1 \le i < j \le n $ . Here, $ | $ is the [bitwise OR operator](https://en.wikipedia.org/wiki/Bitwise_operation#OR).

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10\,000 $ ) — the number of test cases. The first line of each test case contains two integers $ n $ ( $ 2 \le n \le 10^5 $ ) and $ k $ ( $ 1 \le k \le \min(n, 100) $ ). The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le n $ ). It is guaranteed that the sum of $ n $ over all test cases doesn't exceed $ 3 \cdot 10^5 $ .

输出格式

For each test case, print a single integer — the maximum possible value of $\max(i\cdot j-k\cdot(a_i\texttt{ or } a_j))$ .

输入输出样例

输入样例 #1

4
3 3
1 1 3
2 2
1 2
4 3
0 1 2 3
6 6
3 2 0 0 5 6

输出样例 #1

-1
-4
3
12

说明

Let $ f(i, j) = i \cdot j - k \cdot (a_i | a_j) $ . In the first test case, - $ f(1, 2) = 1 \cdot 2 - k \cdot (a_1 | a_2) = 2 - 3 \cdot (1 | 1) = -1 $ . - $ f(1, 3) = 1 \cdot 3 - k \cdot (a_1 | a_3) = 3 - 3 \cdot (1 | 3) = -6 $ . - $ f(2, 3) = 2 \cdot 3 - k \cdot (a_2 | a_3) = 6 - 3 \cdot (1 | 3) = -3 $ . So the maximum is $ f(1, 2) = -1 $ . In the fourth test case, the maximum is $ f(3, 4) = 12 $ .