407474: GYM102801 B Team

Memory Limit:64 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Teamtime limit per test4 secondsmemory limit per test64 megabytesinputstandard inputoutputstandard output

A school has a total of $$$3*n$$$ students, divided evenly into $$$A$$$ group, $$$B$$$ group or $$$C$$$ group, with $$$n$$$ in each group. Everyone has an ability value $$$v_i$$$, the tacit value between two students is $$$f(i,j)=(v_i+v_j)*(v_i \oplus v_j) \% M$$$, where $$$\oplus$$$ means bitwise exclusive OR operation. As the competition coach of this school, you need to select exactly $$$m$$$ teams to participate in the $$$CCPC$$$ competition in the second half of the year.

Specifically, Each team contains exactly three students, and the three students are from different groups. Let the team members from the $$$A,B,C$$$ group be $$$a,b,c$$$, then the tacit value of this team is $$$f(a,b)+f(a,c)$$$.

Please find out the maximum sum of the tacit values of the $$$m$$$ teams.

Input

The input consists of multiple test cases.

The first line contains an integer $$$T$$$ $$$(1 \leq T \leq 10)$$$ — the number of test cases. The description of the test cases follows.

The first line contains three integers $$$n,m,M$$$ $$$(1 \leq m \leq n \leq 200,10 \leq M \leq 2000)$$$.

Then follows three lines, each line contains $$$n$$$ integers $$$v_1,v_2,\dots,v_n$$$ $$$(1 \leq v_i \leq 2000)$$$ — the ability value of each student in group $$$A,B$$$ and $$$C$$$ .

Output

For each test case, print the answer.

ExampleInput
2
3 2 10
1 2 3
4 5 6
7 8 9
4 4 21
5 4 2 6
9 1 10 2
4 3 99 12
Output
27
98

加入题单

上一题 下一题 算法标签: