P9228 Genshin Impact

## 提示：题目背景与题目无关。 你说的对，但是《原神》是由米哈游自主研发的一款全新开放世界冒险游戏。游戏发生在一个被称作「提瓦特」的幻想世界，在这里，被神选中的人将被授予「神之眼」，导引元素之力。你将扮演一位名为「旅行者」的神秘角色，在自由的旅行中邂逅性格各异、能力独特的同伴们，和他们一起击败强敌，找回失散的亲人——同时，逐步发掘「原神」的真相。 因为你的素养很差，我现在每天玩原神都能赚 150 原石，每个月差不多 5000 原石的收入， 也就是现实生活中每个月 5000 美元的收入水平，换算过来最少也 30000 人民币，虽然我 只有 14 岁，但是已经超越了中国绝大多数人（包括你）的水平，这便是原神给我的骄傲的资本。 毫不夸张地说，《原神》是 miHoYo 迄今为止规模最为宏大，也是最具野心的一部作品。即便在经历了 8700 个小时的艰苦战斗后，游戏还有许多尚未发现的秘密，错过的武器与装备，以及从未使用过的法术和技能。 尽管游戏中的战斗体验和我们之前在烧机系列游戏所见到的没有多大差别，但游戏中各类精心设计的敌人以及 Boss 战已然将战斗抬高到了一个全新的水平。就和几年前的《塞尔达传说》一样，《原神》也是一款能够推动同类游戏向前发展的优秀作品。

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**.

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 one integer in one line, representing the answer.

### 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$. | Test Point ID | $n,m \leq$ | Special Property | | :----------: | :----------: | :-----------: | | $1 \sim 5$ | $10$ | | | $6 \sim 10$ | $1000$ | | | $11 \sim 12$ | $10^6$ | $k=0$ | | $13 \sim 14$ | $10^6$ | $k>\max(\max_{i=1}^n\{a_i\},\max_{i=1}^m\{b_i\})$ | | $15 \sim 16$ | $10^6$ | $n=m$ | | $17 \sim 25$ | $10^6$ | | Translated by ChatGPT 5