#2036. 原神

原神

题目描述

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

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

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

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

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

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

输入格式

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

第二行 n n 个整数 a1,a2,⋯ ,an a_1,a_2,\cdots, a_n 。

第三行 m m 个整数 b1,b2,⋯ ,bm 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

题目来源:洛谷 P9228