Дэдпул и Росомаха спасли множество линий времени от полного уничтожения. За это, им, разумеется, полагается награда (конечно, супергероям платят, и при этом много — иначе как бы они позволили себе свои костюмы и оружие).
Всего им выдали $$$n$$$ наград, $$$i$$$-я из которых имеет стоимость $$$a_i$$$. Сначала Логан и Уэйд попробовали разделить награды поровну, то есть так, чтобы каждому досталось множество наград одинаковой суммарной стоимости. Разумеется, у них это сходу не получилось, поэтому после небольшой драки они решили поступить следующим образом:
Разумеется, после потасовки они уже не сильно соображают, да и не факт, что план сработает — УВИ бывают довольно упрямыми, так что задача посчитать, награды какой суммарной стоимости в итоге получит каждый из них, если вдруг все пойдет по плану, выпала вам.
Первая строка содержит число $$$n$$$ — количество наград ($$$1 \le n\le 500$$$).
Следующие $$$n$$$ строк содержат по одному положительному целому числу $$$a_i$$$ — стоимости наград. Гарантируется, что $$$\sum a_i$$$ не превосходит $$$10^5$$$.
Выведите единственное целое число — суммарную стоимость наград, которые каждый заберет домой.
4 2 3 1 6
6
5 2 3 5 8 13
18
В первом примере каждый может сразу получить по $$$6$$$ и в УВИ идти не придется.
Во втором примере каждый может получить по $$$13$$$, после чего останутся награды суммарной стоимостью $$$5$$$. Они будут раздвоены, и каждый получит в сумме $$$18$$$.