Maximizing Pairwise XOR Sum with Bit Flips

You are given an array of length N where each element is an integer less than \(2^K\). You must perform exactly P operations. In each operation, you choose one element and flip one bit in its binary representation (i.e. change a 0 to 1 or a 1 to 0). Note that you are allowed to flip the same bit more than once (thus wasting operations) if needed in order to use exactly P operations.

The goal is to maximize the following value:

\[ S = \sum_{1 \le i < j \le N} a_i \oplus a_j, \]

where \(\oplus\) denotes the bitwise XOR operation.

Explanation: The XOR sum can be computed bit by bit. For a given bit \(j\) (with weight \(2^j\)), if there are \(x\) ones then the contribution from that bit is \(2^j \cdot x \cdot (N-x)\). Since you are allowed exactly P bit flips (with redundant pairs possible), you want to decide, for each bit, which subset of the N numbers to flip (effectively toggling that bit) so that the overall sum of pairwise XORs is maximized. However, you must pick operations across all bits such that the sum of the minimal required flips and any additional wasted (even) flips exactly equals P.

inputFormat

The input consists of two lines. The first line contains three integers N, K, and P (\(1 \le N \le \text{some limit}\), \(1 \le K \le \text{some limit}\), and P is a non-negative integer) separated by spaces. The second line contains N integers \(a_1, a_2, \dots, a_N\), each satisfying \(0 \le a_i < 2^K\).

outputFormat

Print a single integer representing the maximum possible value of \(\displaystyle \sum_{1 \le i < j \le N} a_i \oplus a_j\) that can be achieved after exactly P operations.

sample

3 2 1
1 2 3

6