2315: 火引冰薪
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：52
解决：29
题目描述
《原神》是由米哈游自研的一款全新开放世界冒险RPG。你将在游戏中探索一个被称作「提瓦特」的幻想世界，在「提瓦特」每个人都可以成为神。 你从世界之外漂流而来，降临大地。在这广阔的世界中，你自由旅行、结识同伴、寻找掌控尘世元素的七神，直到与分离的血亲重聚，在终点见证一切旅途的沉淀。 维系者正在死去，创造者尚未到来。面对无法掌控的境遇，人类总会喟叹自身的无力…… 但在人生最陡峭的转折处，若有凡人的渴望达到极致，神明的视线就将投射而下。
在原神中，有一个魔法师，她在一次战斗中，可以打出n次火元素攻击魔法伤害，和m次冰元素攻击魔法伤害，每次攻击的伤害分别为a1，a2，…，an和b1，b2，…，bm。
关于元素攻击之间伤害有如下规则：
1.每次元素攻击可以给没有元素附着的怪物附着相应的元素，初始时怪物没有元素附着；
2.如果用火元素攻击打到冰元素附着的怪物身上，那么本次伤害将 乘2 ，并清空元素附着；
3.如果用冰元素攻击打到火元素附着的怪物身上，那么本次伤害将 加k ，并清空元素附着；
现在魔法师可以任意安排攻击顺序，也就是说，每次攻击过后，魔法师可以自己从没有使用过的魔法中任意挑选一种使用，她希望最大化伤害，请问最大总伤害是多少。
在原神中，有一个魔法师，她在一次战斗中，可以打出n次火元素攻击魔法伤害，和m次冰元素攻击魔法伤害，每次攻击的伤害分别为a1，a2，…，an和b1，b2，…，bm。
关于元素攻击之间伤害有如下规则：
1.每次元素攻击可以给没有元素附着的怪物附着相应的元素，初始时怪物没有元素附着；
2.如果用火元素攻击打到冰元素附着的怪物身上，那么本次伤害将 乘2 ，并清空元素附着；
3.如果用冰元素攻击打到火元素附着的怪物身上，那么本次伤害将 加k ，并清空元素附着；
现在魔法师可以任意安排攻击顺序，也就是说，每次攻击过后，魔法师可以自己从没有使用过的魔法中任意挑选一种使用，她希望最大化伤害，请问最大总伤害是多少。
输入
第一行，三个整数，n，m，k。
第二行，n个整数，表示每次火元素攻击的魔法伤害。
第三行，m个整数，表示每次冰元素攻击的魔法伤害。
第二行，n个整数，表示每次火元素攻击的魔法伤害。
第三行，m个整数，表示每次冰元素攻击的魔法伤害。
输出
一个整数，表示最大总伤害。
样例输入 复制
5 3 5
1 4 2 8 5
7 1 4样例输出 复制
50提示
样例解释：
先用b1攻击，伤害为7，此时附着冰元素；
再用a4攻击，伤害翻倍为16，清空附着元素；
再用a1攻击，伤害为1，此时附着火元素；
再用b2攻击，伤害加5为6，清空附着元素；
再用a2攻击，伤害为4，此时附着火元素；
再用b3攻击，伤害加5为9，清空附着元素；
再用a3攻击，伤害为2，此时附着火元素；
再用a5攻击，伤害为5，此时附着火元素；
总伤害为7+16+1+6+4+9+2+5=50。
数据范围：
对于 100% 的分数，1≤n，m≤1e6，0≤ai，bi，k≤1e9。
先用b1攻击，伤害为7，此时附着冰元素；
再用a4攻击，伤害翻倍为16，清空附着元素；
再用a1攻击，伤害为1，此时附着火元素；
再用b2攻击，伤害加5为6，清空附着元素；
再用a2攻击，伤害为4，此时附着火元素；
再用b3攻击，伤害加5为9，清空附着元素；
再用a3攻击，伤害为2，此时附着火元素；
再用a5攻击，伤害为5，此时附着火元素；
总伤害为7+16+1+6+4+9+2+5=50。
数据范围：
对于 100% 的分数，1≤n，m≤1e6，0≤ai，bi，k≤1e9。