题目描述

小y 手里有 $n$ 张卡牌，第 $i$ 张卡牌的数值大小为 $a_i$，他想要成为卡牌大师，于是打算施展一些魔法，为了让自己手中的 $n$ 张卡牌数值之和最大。

施展魔法需要用到三张卡牌，$(i,j,k)$，施展魔法之后会将 $a_i$ 和 $a_j$ 更新为 $0$，将 $a_k$ 更新为 $(a_k*2)$。

题目不限制施法次数，要求不可以重复使用之前施过法的卡牌，问最后 $n$ 张卡牌的数值之和 最大是多少？

数据范围

对于 $100$%的数据： $1≤n≤2*10^5,1≤a_i≤10^9$。

输入格式

第一行输入一个整数 $n$，表示卡牌的数量。

第二行输入 $n$ 个整数，$a_i$ 表示第 $i$ 张卡牌的数值大小。

输出格式

施法之后 $n$ 张卡牌的数值之和最大值。

8
1 2 6 6 6 3 4 5

36

4
6 7 8 9

30

8
1 2 6 6 6 2 1 5

35

提示

样例数据1解释：

施法的三张卡牌编号 $(i,j,k)$ 分别为 $1,2,3$，所以施法之后 $n$ 张卡牌的数值分别为 $[0,0,12,6,6,3,4,5]$

数值和为 $36$。

样例数据2解释： 不进行施法时，整数之和最大。

样例数据3解释：施法两次