B. Cobb

B. Cobb

原文链接Problem - 1554B - Codeforces

B. Cobb

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given nn integers a1,a2,…,ana1,a2,…,an and an integer kk. Find the maximum value of i⋅j−k⋅(ai|aj)i⋅j−k⋅(ai|aj) over all pairs (i,j)(i,j) of integers with 1≤i<j≤n1≤i<j≤n. Here, || is the bitwise OR operator.

Input

The first line contains a single integer tt (1≤t≤100001≤t≤10000)  — the number of test cases.

The first line of each test case contains two integers nn (2≤n≤1052≤n≤105) and kk (1≤k≤min(n,100)1≤k≤min(n,100)).

The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (0≤ai≤n0≤ai≤n).

It is guaranteed that the sum of nn over all test cases doesn't exceed 3⋅1053⋅105.

Output

For each test case, print a single integer  — the maximum possible value of i⋅j−k⋅(ai|aj)i⋅j−k⋅(ai|aj).

Example

input

Copy

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

output

Copy

-1
-4
3
12

Note

Let f(i,j)=i⋅j−k⋅(ai|aj)f(i,j)=i⋅j−k⋅(ai|aj).

In the first test case,

• f(1,2)=1⋅2−k⋅(a1|a2)=2−3⋅(1|1)=−1f(1,2)=1⋅2−k⋅(a1|a2)=2−3⋅(1|1)=−1.
• f(1,3)=1⋅3−k⋅(a1|a3)=3−3⋅(1|3)=−6f(1,3)=1⋅3−k⋅(a1|a3)=3−3⋅(1|3)=−6.
• f(2,3)=2⋅3−k⋅(a2|a3)=6−3⋅(1|3)=−3f(2,3)=2⋅3−k⋅(a2|a3)=6−3⋅(1|3)=−3.

So the maximum is f(1,2)=−1f(1,2)=−1.

In the fourth test case, the maximum is f(3,4)=12f(3,4)=12.

----------------------------------------------------------------------------------------------------------------------------

这题直接枚举会超时，利用一些性质更是无处下手。

突破点在数据范围，a[i]<=n  

按位或运算性质如下

a|b>=max(a,b)

a|b<=a+b

我们考虑数据范围极大的情况，最后那一段，n*(n-1)-(an|an-1)*k,我们取最坏情况

an|an-1==2n

n*(n-1)-2n*100    =n*(n-1)-200*n=  n*(n-201)  这个其实也就是an-201 和an搭配的情况，但是没减去后面“ k⋅(ai|aj)” 所以an和an-1搭配一定大于an和an-201搭配

所以以此类推，保持n不动 ,n*(n-1)-2n*100 中(n-1)一直减小到a-200,又会得到一部分在an和an-201之前的搭配，且分别优于他们，然后按照这个规律，一直减少n*(n-1)，都会在前面找到一个与之对应的，并且还由于前面的。

这样最多可以向前面推大约200*200项，再把推出来的继续往前，结果只会更差

# include<iostream>
# include<stack>
# include<cstring>
# include<math.h>
# include<map># include<iomanip>
using namespace std;
typedef long long int ll;ll a[100000+10];
int main( )
{int t;cin>>t;while(t--){ll n,k;cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];}ll ans=-9999999999999;for(ll i=n;i>=max((ll)1,n-201);i--){for(ll j=n;j>=max((ll)1,n-201);j--){if(i!=j)ans=max(ans,(i*j)-k*(a[i]|a[j]));}}cout<<ans<<'n';}return 0;
}