Илья — очень добрый лев, который любит математику. Из всех математических объектов Илья больше всего любит матрицы. Сейчас перед ним стоит непростая задача о матрицах, которую нужно решить.
Заданы квадратная матрица размера 2n × 2n и 4n целых чисел. Нужно разместить все эти числа в матрице (каждое число поместить в отдельную ячейку) так, чтобы красота полученной матрицы с числами была максимальна.
Красотой матрицы размера 2n × 2n называется целое число, получаемое по следующему алгоритму:
- Найти максимальный элемент в матрице. Обозначим его за m.
- Если n = 0, тогда красота матрицы равна m. Иначе, матрицу можно разбить на 4 непересекающиеся подматрицы размера 2n - 1 × 2n - 1, тогда красота матрицы равна сумме числа m и четырех красот описанных подматриц.
Как можно заметить, этот алгоритм — рекурсивный.
Помогите Илье, решите задачу и выведите результирующую максимальную красоту матрицы.
Выходные данные
В единственную строку выведите максимальное значение красоты полученной матрицы.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примечание
Рассмотрим второй пример, числа в матрице надо расставить следующим способом:
1 2
3 4
Тогда красота матрицы будет равна: 4 + 1 + 2 + 3 + 4 = 14.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
13
|
13
|
|
2
|
4
1 2 3 4
|
14
|