Гусейн и его младший брат нашли на улице кошелек с $n$ банкнотами. Поскольку владельца денег найти не удалось, они решили разделить деньги между собой. Они поделили деньги между собой так, чтобы каждому досталось одинаковое количество денег. В это время могло остаться наименьшее количество денег, которое можно было оставить. Гусейн забирает эти деньги, потому что он старший брат. Определите сумму денег, которая досталась Гусейну. \InputFile В первой строке записано целое число $n~(1 \le n \le 500)$ --- количество банкнот в кошельке. В каждой из следующих строк указано одно целое положительное значение $c_i$ --- стоимость $i$-ой банкноты (в манатах). Известно, что $c_1 + ... + c_n \le 10^5$. \OutputFile Выведите сумму денег, которая досталась Гусейну. \Examples Пример 1. Гусейн может взять банкноту в $10$ манат, а его брат может взять остальные купюры. Пример 2. В первоначальной раздаче Гусейн может взять банкноту в $19$ манат, а его брат может взять банкноту в $17$ манат и $2$ маната. В этом случае банкнота номиналом $3$ маната достаётся Гусейну. Таким образом Гусейн получит $19 + 3 = 22$ маната.