You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

提示：题目背景与题目无关。

你说的对，但是《原神》是由米哈游自主研发的一款全新开放世界冒险游戏。游戏发生在一个被称作「提瓦特」的幻想世界，在这里，被神选中的人将被授予「神之眼」，导引元素之力。你将扮演一位名为「旅行者」的神秘角色，在自由的旅行中邂逅性格各异、能力独特的同伴们，和他们一起击败强敌，找回失散的亲人——同时，逐步发掘「原神」的真相。

因为你的素养很差，我现在每天玩原神都能赚 150 原石，每个月差不多 5000 原石的收入， 也就是现实生活中每个月 5000 美元的收入水平，换算过来最少也 30000 人民币，虽然我 只有 14 岁，但是已经超越了中国绝大多数人（包括你）的水平，这便是原神给我的骄傲的资本。

毫不夸张地说，《原神》是 miHoYo 迄今为止规模最为宏大，也是最具野心的一部作品。即便在经历了 8700 个小时的艰苦战斗后，游戏还有许多尚未发现的秘密，错过的武器与装备，以及从未使用过的法术和技能。

尽管游戏中的战斗体验和我们之前在烧机系列游戏所见到的没有多大差别，但游戏中各类精心设计的敌人以及 Boss 战已然将战斗抬高到了一个全新的水平。就和几年前的《塞尔达传说》一样，《原神》也是一款能够推动同类游戏向前发展的优秀作品。

题目描述

原神中有一个魔法师，她可以打出 $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$。

输出格式

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

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

提示

样例 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$。

数据规模与约定

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