Гусейн и его младший брат нашли на улице кошелек с n банкнотами. Поскольку владельца денег найти не удалось, они решили разделить деньги между собой. Они поделили деньги между собой так, чтобы каждому досталось одинаковое количество денег. В это время могло остаться наименьшее количество денег, которое можно было оставить. Гусейн забирает эти деньги, потому что он старший брат.
Определите сумму денег, которая досталась Гусейну.
В первой строке записано целое число n (1≤n≤500) — количество банкнот в кошельке. В каждой из следующих строк указано одно целое положительное значение ci — стоимость i-ой банкноты (в манатах). Известно, что c1+...+cn≤105.
Выведите сумму денег, которая досталась Гусейну.
Пример 1. Гусейн может взять банкноту в 10 манат, а его брат может взять остальные купюры.
Пример 2. В первоначальной раздаче Гусейн может взять банкноту в 19 манат, а его брат может взять банкноту в 17 манат и 2 маната. В этом случае банкнота номиналом 3 маната достаётся Гусейну. Таким образом Гусейн получит 19+3=22 маната.