Поделить деньги
Гусейн и его младший брат нашли на улице кошелек с банкнотами. Поскольку владельца денег найти не удалось, они решили разделить деньги между собой. Они поделили деньги между собой так, чтобы каждому досталось одинаковое количество денег. В это время могло остаться наименьшее количество денег, которое можно было оставить. Гусейн забирает эти деньги, потому что он старший брат.
Определите сумму денег, которая досталась Гусейну.
Вхідні дані
В первой строке записано целое число — количество банкнот в кошельке. В каждой из следующих строк указано одно целое положительное значение — стоимость -ой банкноты (в манатах). Известно, что .
Вихідні дані
Выведите сумму денег, которая досталась Гусейну.
Приклади
Пример 1. Гусейн может взять банкноту в манат, а его брат может взять остальные купюры.
Пример 2. В первоначальной раздаче Гусейн может взять банкноту в манат, а его брат может взять банкноту в манат и маната. В этом случае банкнота номиналом маната достаётся Гусейну. Таким образом Гусейн получит маната.