예쁜 꽃다발

면접 대비

시간 제한1초메모리 제한512 MB

요약

꽃 종류별 재고가 주어질 때, 각 종류에서 홀수 개를 골라 전체 개수가 홀수가 되면서 최대가 되도록 만든다.

난이도: 쉬움10점 중 3점
유형: 그리디, 수학, 구현
정답자: 아직 제출이 없습니다

문제

Maxim은 여자친구 Ira의 생일을 맞아 꽃다발을 선물하려고 한다.

Maxim의 집 근처 꽃집에서는 $n$ 종류의 꽃을 판다. 가게에 $i$ 번째 종류의 꽃이 $a_i$ 송이 있다는 것을 Maxim은 알고 있다. Ira가 홀수를 좋아한다는 사실도 알고 있다. 그래서 Maxim은 꽃다발에 각 종류의 꽃이 홀수 송이씩 들어가야 하고, 꽃다발에 담기는 꽃의 총 개수도 홀수여야 한다고 정했다.

꽃다발에 담을 수 있는 꽃의 최대 개수를 Maxim이 구하도록 도와주자.

입력

첫째 줄에 정수 $n$ 이 주어진다. $n$ 은 가게에서 파는 꽃의 종류 수이다 ( $1 \le n \le 100\,000$ ).

둘째 줄에 $n$ 개의 정수 $a_1, a_2, \ldots, a_n$ 이 주어진다. $a_i$ 는 각 종류의 꽃 개수이다 ( $1 \le a_i \le 1000$ ).

출력

꽃다발에 담을 수 있는 꽃의 최대 개수를 한 줄에 출력한다.

예제2

예제 1
입력
```
3
3 5 8
```
예상 출력
```
15
```
예제 2
입력
```
3
1 1 1
```
예상 출력
```
3
```