← 返回题目列表

Codeforces · 313/C

C. 伊利亚和矩阵

中文机器翻译题面 查看原题

伊利亚是一只性情非常善良的狮子。他喜欢数学。在所有数学对象中,他最喜欢的是矩阵。现在他面临着一个需要解决的复杂矩阵问题。

他有一个 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。