Problem Description

In Genshin Impact, there is a mage who can cast $n$ Pyro attacks and $m$ Cryo attacks. The damage of each attack is $a_1,a_2,\cdots, a_n$ and $b_1,b_2,\cdots, b_m$, respectively.

The following reaction rules exist between elemental attacks:

• Each elemental attack can apply the corresponding element to a monster with no elemental aura. Initially, the monster has no elemental aura.

• If a Pyro attack hits a monster with a Cryo aura, then the damage of this attack will be $\times 2$, and the elemental aura is cleared.

• If a Cryo attack hits a monster with a Pyro aura, then the damage of this attack will be $+k$, and the elemental aura is cleared.

Now the mage may arrange the attack order arbitrarily. That is, after each attack, the mage can choose any unused spell to cast next. She wants to maximize the total damage. Find the maximum total damage.

Input Format

The first line contains three integers $n,m,k$.

The second line contains $n$ integers $a_1,a_2,\cdots, a_n$.

The third line contains $m$ integers $b_1,b_2,\cdots, b_m$.

Output Format

Output one integer in one line, representing the answer.

6 7 3
1 1 4 5 1 4
1 9 1 9 8 1 0

67

5 3 5
1 4 2 8 5
7 1 4

50

1 1 0
2
3

7

见附件中的 samples/genshin4.in

见附件中的 samples/genshin4.ans

见附件中的 samples/genshin5.in

见附件中的 samples/genshin5.ans

Hint

Explanation for Sample 1

Use the order $a_1\rightarrow b_4\rightarrow a_2\rightarrow b_3\rightarrow a_5\rightarrow b_5\rightarrow b_7 \rightarrow b_1\rightarrow a_3 \rightarrow b_2\rightarrow a_4\rightarrow b_6 \rightarrow a_6$. The actual damage each time is $1,12,1,4,1,11,0,1,8,9,10,1,8$, and the total damage is $67$.

Explanation for Sample 2

Use the order $a_5\rightarrow b_1\rightarrow b_2\rightarrow a_4\rightarrow a_3\rightarrow b_3\rightarrow a_2\rightarrow a_1$. The actual damage each time is $5,12,1,16,2,9,4,1$, and the total damage is $50$.

Constraints

For $100\%$ of the testdata, $1 \leq n,m \leq 10^6$, $0 \leq a_i,b_i,k \leq 10^9$.

Translated by ChatGPT 5