Problem description

W szkole Jasia jest N klas. Kilka z tych klas ma odbyć wspólną lekcję wuefu, na której będą grały w piłkę. Żeby gra była uczciwa, wszystkich uczestników należy podzielić na dwie drużyny składające się z takiej samej liczby osób. Z drugiej strony, żeby gra była fajna, sumarycznie uczestników powinno być jak najwięcej.

Oczywiście nie można podzielić klasy na części – albo cała klasa bierze udział w lekcji albo nikt z danej klasy nie bierze w niej udziału. Może się jednak zdarzyć, że dwie osoby z tej samej klasy zostaną przydzielone do różnych drużyn.

Napisz program, który wczyta liczbę klas oraz liczebność każdej z nich, a następnie wypisze, ile osób może wziąć udział w łączonym wuefie przy najlepszym możliwym wyborze klas.

Wejście

W pierwszym wierszu wejścia znajduje się jedna dodatnia liczba naturalna N oznaczająca liczbę klas.
W drugim wierszu wejścia znajduje się N dodatnich liczb naturalnych, poodzielanych pojedynczymi odstępami. Oznaczają one liczebności kolejnych klas.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita będąca największą możliwą liczbą uczestników łączonego wuefu.

Ograniczenia

1 ≤ N ≤ 1 000 000
Każda klasa ma nie więcej niż 10⁹ uczniów.

Przykład

4
2 4 3 2

8

1
5

0

5
2 6 3 2 1

14