题目描述

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

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

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

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

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

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

输入格式

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

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

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

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

输出格式

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

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 解释

攻击采用 $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$，每次的实际伤害为 $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$。