Problem Description

In Genshin Impact, there is a mage who can cast $n$ fire elemental attack spells and $m$ ice elemental attack spells, with each attack dealing damage $a_1, a_2, \cdots, a_n$ and $b_1, b_2, \cdots, b_m$ respectively.

Elemental attacks have the following reaction rules:

• Each elemental attack can attach the corresponding element to a monster that has no element attached. Initially, the monster has no element attached.
• If a fire elemental attack hits a monster with ice element attached, the damage will be doubled and the element attachment will be cleared.
• If an ice elemental attack hits a monster with fire element attached, the damage will be increased by $k$ and the element attachment will be cleared.

The mage can arrange the attack sequence arbitrarily, meaning that after each attack, the mage can choose any unused spell from her repertoire. She aims to maximize the total damage. What is 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

A single line containing one integer, representing the answer.

Sample Input and Output

Input Sample #1

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

Output Sample #1

67

Input Sample #2

5 3 5
1 4 2 8 5
7 1 4

Output Sample #2

50

Input Sample #3

1 1 0
2
3

Output Sample #3

7

Input Sample #4

See attachment samples/genshin4.in

Output Sample #4

See attachment samples/genshin4.ans

Input Sample #5

See attachment samples/genshin5.in

Output Sample #5

See attachment samples/genshin5.ans

Notes

Sample 1 Explanation

The attacks are arranged as $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_3 \rightarrow a_6$, with actual damage of $1, 12, 1, 4, 1, 11, 0, 1, 8, 9, 10, 1, 8$, totaling $67$.

Sample 2 Explanation

The attacks are arranged as $a_5 \rightarrow b_1 \rightarrow b_2 \rightarrow a_4 \rightarrow a_3 \rightarrow b_3 \rightarrow a_2 \rightarrow a_1$, with actual damage of $5, 12, 1, 16, 2, 9, 4, 1$, totaling $50$.

Data Size and Constraints

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

见题面 Input 部分

见题面 Output 部分