Description

原神中有一个魔法师，她可以打出 $n$ 次火元素攻击魔法和 $m$ 次冰元素攻击魔法，每次攻击的伤害分别为 $a_1,a_2,\cdots, a_n$ 和 $b_1,b_2,\cdots, b_m$。

元素攻击之间存在如下反应规则：

• 每次元素攻击可以给没有元素附着的怪物附着相应的元素，初始时怪物没有元素附着；

• 如果用火元素攻击打到冰元素附着的怪物身上，那么本次伤害将 $\times 2$，并清空元素附着；

• 如果用冰元素攻击打到火元素附着的怪物身上，那么本次伤害将 $+k$，并清空元素附着。

现在魔法师可以任意安排攻击顺序，也就是说，每次攻击过后，魔法师可以从自己没有使用过的魔法中任意挑选一种使用。她希望最大化总伤害，请问最大总伤害是多少。

Input Format

第一行三个整数 $n,m,k$。

第二行 $n$ 个整数 $a_1,a_2,\cdots, a_n$。

第三行 $m$ 个整数 $b_1,b_2,\cdots, b_m$。

Output Format

一行一个整数，表示答案。

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

样例 1 解释

攻击采用 $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$，每次的实际伤害为 $1,12,1,4,1,11,0,1,8,9,10,1,8$，总伤害为 $67$。

样例 2 解释

攻击采用 $a_5\rightarrow b_1\rightarrow b_2\rightarrow a_4\rightarrow a_3\rightarrow b_3\rightarrow a_2\rightarrow a_1$，每次的实际伤害为 $5,12,1,16,2,9,4,1$，总伤害为 $50$。

数据规模与约定

对于 $100\%$ 的数据，$1 \leq n,m \leq 10^6$，$0 \leq a_i,b_i,k \leq 10^9$。