Sharmeen, the little girl has a friend named Mozahid. It is Eid day and they collect ‘Salami’s :P from their relatives. But as they are good friends, they want to divide the total amount of taka into two equal parts. But every time it is not possible, so they came with a solution. They can give any ‘salami’ to any poor people to help him, but there is a restriction. If they give a ‘salami’ to a poor, they have to give the whole ‘salami’. After helping the poor, they can add all the ‘salami’ amounts and divide it into two equal parts if possible, there is no restriction. But the divided amount must be integer. For example if the ‘salami’s are {3, 5, 1} you can’t divide (3+5+1)=9 into two equal parts. But if you give 5 taka to a poor people you can divide (3+1) = 4 into two equal parts 2 , 2. They want help the poor people(They are also allowed not to help any) in such a way that, the amount they get after dividing the remaining amount into two equal parts is maximum possible.

Input

The first line of the input is an integer n which is the number of ‘salami’s.

The next line contains n integers A[i] which are the amount of each ‘salami’.

Output

Output the amount Sharmeen will get after distribution.

Constrain:

1 <= n <= 10⁵

1 <= A[i] <= 10⁹

Example

Input:
3
8 2 5

Output:
5

Explanation:

As (8 + 2 + 5) = 15, which can’t be divided into two equal parts. They can give 5 taka to any poor people and divide the rest total into two equal parts. (8 + 2) = 10 , 10 / 2 = 5 . So, Sharmeen will get 5 taka.