Attractive Flowers

Interview

Time limit1sMemory limit512 MB

Summary

Given the stock of each flower type, pick an odd count from each type so the total is odd and as large as possible.

Level: Easy3 of 10
Topics: Greedy, Math, Implementation
Solved: No attempts yet

Problem

Maxim wants to give his girlfriend Ira a bouquet of flowers for her birthday.

The flower shop near his house sells flowers of $n$ types. Maxim has found out that the store has $a_i$ flowers of the $i$ -th type. He also knows that Ira likes odd numbers. So Maxim has decided that the bouquet must contain an odd number of flowers of each type, and the total number of flowers in the bouquet must also be odd.

Help Maxim find the maximum number of flowers the bouquet can contain.

Input

The first line contains an integer $n$ , the number of flower types sold in the store ( $1 \le n \le 100\,000$ ).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ , the number of flowers of each type ( $1 \le a_i \le 1000$ ).

Output

Print the maximum number of flowers the bouquet can contain on one line.

Examples2

Example 1
Input
```
3
3 5 8
```
Expected output
```
15
```
Example 2
Input
```
3
1 1 1
```
Expected output
```
3
```