Награда за спасение мультивселенной
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дэдпул и Росомаха спасли множество линий времени от полного уничтожения. За это, им, разумеется, полагается награда (конечно, супергероям платят, и при этом много — иначе как бы они позволили себе свои костюмы и оружие).

Всего им выдали $$$n$$$ наград, $$$i$$$-я из которых имеет стоимость $$$a_i$$$. Сначала Логан и Уэйд попробовали разделить награды поровну, то есть так, чтобы каждому досталось множество наград одинаковой суммарной стоимости. Разумеется, у них это сходу не получилось, поэтому после небольшой драки они решили поступить следующим образом:

  1. для начала выбрать два непересекающихся набора наград одинаковой суммарной стоимости $$$s$$$; наборы должны быть выбраны таким образом, чтобы $$$s$$$ было максимально;
  2. затем отнести все оставшиеся награды в УВИ и убедить их раздвоить каждую из них (забрать вариант той же награды из другой линии времени), чтобы затем можно было и их тоже поделить поровну.

Разумеется, после потасовки они уже не сильно соображают, да и не факт, что план сработает — УВИ бывают довольно упрямыми, так что задача посчитать, награды какой суммарной стоимости в итоге получит каждый из них, если вдруг все пойдет по плану, выпала вам.

Входные данные

Первая строка содержит число $$$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$$$.