Problem Background

kls is a winner.

Problem Description

kls has recently been playing a game similar to 2048. The rules are as follows:

Initially, there are $n$ blocks, each with an integer between $1$ and $m$.

kls can perform two types of operations:

1. Select two blocks with the same number (not necessarily adjacent) and merge them into one block with a number twice the original.
2. Decrease the number on a block.

There is no limit to the number of operations, and the final score is the largest number on any block.

Since kls has to go accompany his girlfriend and doesn't have time to continue playing, he wants you to help calculate the maximum score he can achieve.

Input and Output Format

Input Format

Due to the potential size of the data, reading input can be time-consuming, so kls provides a C++ random number generator.

void generate_array(int a[], int n, int m, int seed) {
    unsigned x = seed;
    for (int i = 0; i < n; ++i) {
        x ^= x << 13;
        x ^= x >> 17;
        x ^= x << 5;
        a[i] = x % m + 1;
    }
}

Copy this function into your program. Use an array large enough, and input data given $n$, $m$, and $seed$ as parameters to call this function. The array will then contain the initial numbers on the blocks (index starts from 0).

Input consists of three numbers $n, m, seed$, as described above.

Output Format

Output a single number, representing the maximum score.

Sample Input and Output

Sample Input #1

5 10 233

Sample Output #1

24

Sample Input #2

5 50 3

Sample Output #2

48

Sample Input #3

1000 1000 666

Sample Output #3

374784

Notes

Sample Explanation

For Sample 1, the generated numbers are 6, 10, 7, 5, 4.

For Sample 2, the generated numbers are 8, 12, 48, 4, 4.

Data Range

For 30% of the data, $n, m \le 10$;

For 60% of the data, $n, m \le 10^5$;

For 100% of the data, $n, m \le 10^7$, $1 \le seed \le 10^9$.

见题面 Input 部分

见题面 Output 部分