You are given an array of ~N~ integers. A modification consists of selecting two distinct indices in the array that point to positive integers in the array and decreasing both integers by 1.

Compute the maximum number of modifications you can perform on the array until you can no longer perform any modifications.

Constraints

~1 \le N \le 50~

~1 \le a_i \le 10^9~

In tests worth 5 marks, the sum of all ~a_i~ will be less than or equal to ~10^5~.

Input Specification

The first line contains a single integer, ~N~.

Each of the next ~N~ lines contains a single integer, ~a_1~ through ~a_N~ in order.

Output Specification

Print, on a single line, the maximum number of modifications that can be performed.

Sample Input 1

3
1
2
1

Sample Output 1

2

Sample Input 2

5
1
2
1
10
3

Sample Output 2

7