У вас есть \(n\) сундуков. \(i\)-й сундук содержит \(a_i\) монет. Вы должны открыть все \(n\) сундуков по порядку, начиная с сундука \(1\), заканчивая сундуком \(n\).
Также существуют два вида ключей, которые вы можете использовать для открытия каждого сундука:
- хороший ключ, который стоит \(k\) монет;
- плохой ключ, который бесплатен, но уменьшит вдвое количество монет в каждом неоткрытом сундуке, включая сундук, который собираются им открыть. Уменьшаясь вдвое, количество монет округляется вниз до ближайшего целого числа для каждого из сундуков. Иными словами, если используется плохой ключ, чтобы открыть сундук \(i\), количества монет в сундуках изменятся следующим образом: \(a_i = \lfloor{\frac{a_i}{2}\rfloor}\), \(a_{i+1} = \lfloor\frac{a_{i+1}}{2}\rfloor, \dots, a_n = \lfloor \frac{a_n}{2}\rfloor\);
- любой ключ (и хороший и плохой) ломается после использования, то есть является одноразовым.
Вам необходимо использовать \(n\) ключей, по одному на каждый сундук. Изначально у вас нет ключей и монет. Если вы хотите использовать хороший ключ, то его надо купить.
В процессе вы можете уходить в минус — например, если у вас есть \(1\) монета, вы можете купить хороший ключ за \(k=3\) монеты, и у вас станет \(-2\) монеты.
Найдите максимальное количество монет, которое вы сможете получить в итоге после открытия всех \(n\) сундуков по порядку от \(1\) до \(n\).
Выходные данные
Для каждого набора выведите одно число — максимальное количество монет, которое вы сможете получить после открытия сундуков с \(1\) по \(n\).
Пожалуйста, обратите внимание, что ответ для некоторых наборов входных данных может не поместиться в 32-разрядный целочисленный тип, поэтому вы должны использовать по крайней мере 64-разрядный целочисленный тип в вашем языке программирования (например, long long для C++).
Примечание
В первом наборе одна из возможных стратегий следующая:
- Купить хороший ключ за \(5\) монет, и открыть сундук \(1\), получив \(10\) монет. Ваш баланс станет \(0 + 10 - 5 = 5\) монет.
- Купить хороший ключ за \(5\) монет, и открыть сундук \(2\), получив \(10\) монет. Ваш баланс станет \(5 + 10 - 5 = 10\) монет.
- Использовать плохой ключ, и открыть им сундук \(3\). В результате использования плохого ключа, количество монет в сундуке \(3\) становится \(\left\lfloor \frac{3}{2} \right\rfloor = 1\), и количество монет в сундуке \(4\) становится \(\left\lfloor \frac{1}{2} \right\rfloor = 0\). Ваш баланс станет \(10 + 1 = 11\).
- Использовать плохой ключ, и открыть им сундук \(4\). В результате использования плохого ключа, количество монет в сундуке \(4\) станет \(\left\lfloor \frac{0}{2} \right\rfloor = 0\). Ваш баланс станет \(11 + 0 = 11\).
После открытия всех сундуков, у вас останется
\(11\) монет. Можно доказать, что получить больше монет невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4 5
10 10 3 1
1 2
1
3 12
10 10 29
12 51
5 74 89 45 18 69 67 67 11 96 23 59
2 57
85 60
|
11
0
13
60
58
|