伊利亚是一只性情非常善良的狮子。他喜欢数学。在所有数学对象中,他最喜欢的是矩阵。现在他面临着一个需要解决的复杂矩阵问题。
他有一个 2n × 2n 大小的方阵和 4n 个整数。您需要将所有这些数字排列在矩阵中(将每个数字放在一个单独的单元格中),以便得到的数字矩阵的美观度最大化。
2n×2n大小的矩阵的美是一个整数,通过以下算法获得:
1. 找出矩阵中的最大元素。我们将其表示为m。
2.如果n = 0,则矩阵的美度等于m。否则,可以将一个矩阵分割为4个不相交的2n - 1 × 2n - 1大小的子矩阵,则该矩阵的美度等于数m与所描述的子矩阵的其他4个美度之和。
如您所见,该算法是递归的。
帮助 Ilya 解决问题并打印出矩阵的最大美感。
输入
第一行包含整数 4n (1 ≤ 4n ≤ 2·106)。下一行包含 4n 个整数 ai (1 ≤ ai ≤ 109) — 您需要在 2n × 2n 大小的矩阵中排列的数字。
输出
在一行上打印所描述的矩阵的美度的最大值。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
示例
输入 #1
1 13
输出 #1
13
输入 #2
4 1 2 3 4
输出 #2
14
注意
考虑第二个示例。您需要按如下方式排列矩阵中的数字:
那么矩阵的美度就等于:4 + 1 + 2 + 3 + 4 = 14。