Lent Money

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/JUNE19/hindi/LENTMO.pdf), [Bengali](http://www.codechef.com/download/translated/JUNE19/bengali/LENTMO.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/JUNE19/mandarin/LENTMO.pdf), [Russian](http://www.codechef.com/download/translated/JUNE19/russian/LENTMO.pdf), and [Vietnamese](http://www.codechef.com/download/translated/JUNE19/vietnamese/LENTMO.pdf) as well. Chef lent some money to Chefexim. He has been asking for his money back for a long time, but Chefexim always comes up with an excuse. This time, Chef got really angry, since he needed the money to buy some ingredients for his ladoos, and Chefexim decided to return the money he borrowed. Knowing Chef's love of challenges, Chefexim gave Chef a challenge along with the money in order to keep him calm and happy. Chefexim divided the money he borrowed from Chef into $N$ bags (numbered $1$ through $N$); for each valid $i$, the $i$th bag contains $A_i$ units of money. Then, he gave all $N$ bags to Chef along with two integers $K$ and $X$. Now, Chef may perform the following operation any number of times (including zero):  Pick exactly $K$ different bags with numbers $i_1, i_2, \ldots, i_K$ ($1 \le i_j \le N$ for each valid $j$).  Change the amounts of money inside the selected bags. For each $j$ ($1 \le j \le K$), the amount of money inside the $i_j$th bag is changed from $A_{i_j}$ to $A_{i_j} \oplus X$. Here, $\oplus$ denotes the bitwise XOR operation. Each bag may be picked any number of times in different operations. Find the maximum total amount of money (sum of amounts of money in all the bags) Chef can have at the end if he performs the operations optimally. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains a single integer $N$.  The second line contains $N$ spaceseparated integers $A_1, A_2, \ldots, A_N$ denoting the initial amounts of money inside the bags.  The third line contains a single integer $K$.  The fourth line contains a single integer $X$. ### Output For each test case, print a single line containing one integer — the maximum amount of money Chef can have. ### Constraints  $1 \le T \le 100$  $1 \le N \le 10^4$  $1 \le K \le N$  $0 \le A_i \le 10^9$ for each valid $i$  $0 \le X \le 10^9$ ### Subtasks **Subtask #1 (10 points):** $1 \le N \le 10$ **Subtask #2 (10 points):**  $1 \le N \le 100$  $0 \le A_i \le 1$ for each valid $i$  $0 \le X \le 1$ **Subtask #3 (80 points):** original constraints ### Example Input ``` 2 5 1 2 3 4 5 2 4 7 10 15 20 13 2 1 44 4 14 ``` ### Example Output ``` 23 129 ``` ### Explanation **Example case 1:** Chef can perform two operations. 1. Pick the bags $1$ and $4$, change the amount of money in bag $1$ to $1 \oplus 4 = 5$ and the amount of money in bag $4$ to $4 \oplus 4 = 0$. After this operation, the sequence $A = (5, 2, 3, 0, 5)$. 2. Pick the bags $2$ and $3$, change the amount of money in bag $2$ to $2 \oplus 4 = 6$ and the amount of money in bag $3$ to $3 \oplus 4 = 7$. After this operation, $A = (5, 6, 7, 0, 5)$. At the end, the total amount of money is $5+6+7+0+5 = 23$, which is maximum possible. **Example case 2:** Chef can pick the bags $1$, $3$, $5$ and $6$, change the amount of money in bag $1$ to $10 \oplus 14 = 4$, the amount of money in bag $3$ to $20 \oplus 14 = 26$, the amount of money in bag $5$ to $2 \oplus 14 = 12$ and the amount of money in bag $6$ to $1 \oplus 14 = 15$. Afterwards, $A = (4, 15, 26, 13, 12, 15, 44)$ and the total amount of money is $129$, which is maximum possible.Author:  ucntstopme 
Editorial  https://discuss.codechef.com/problems/LENTMO 
Tags  june19, junechallenge, ucntstopme 
Date Added:  24042019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 