ДИО знает, что Крестоносцы звёздной пыли определили его местоположение и собираются сразиться с ним. Чтобы сорвать их планы, он решает послать несколько пользователей стендов для борьбы с ними. Первоначально он призвал с собой \(n\) пользователей, причем сила \(i\)-го из них равна \(a_i\). Используя свои вампирические способности, он может делать следующее столько раз, сколько пожелает:
К несчастью для ДИО, используя предсказательные способности Пурпурного отшельника, Крестоносцы знают, что он замышляет это, и они также знают силы первоначальных пользователей стендов. Помогите Крестоносцам найти максимально возможную силу пользователя стенда среди всех возможных способов вызовов.
Выходные данные
Для каждого набора входных данных выведите одно целое число, максимальную силу пользователя Стенда среди всех возможных способов вызовов.
Примечание
В первом наборе входных данных один из способов добавления новых пользователей Стендов выглядит следующим образом:
- Выбрать \(i=n\). Теперь \(a\) становится \([0,2,5,1,1]\).
- Выбрать \(i=1\). Теперь \(a\) становится \([0,2,5,1,1,7]\). \(7\) — это максимальная сила пользователя стенда, которого может вызвать ДИО.
Во втором наборе входных данных, ДИО не нужно добавлять больше пользователей стенда, потому что \(3\) — это максимальная сила пользователя стенда, которого ДИО может вызвать.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4
0 2 5 1
3
1 2 3
5
8 2 4 12 1
|
7
3
14
|