준석이의 사탕 사기

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

요약

사탕 봉지 N개 중 일부를 골라 합이 짝수가 되는 최댓값을 구합니다. 그런 합이 없으면 0을 출력합니다.

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

문제

준석이는 두 동생을 위해 사탕 가게에서 사탕을 최대한 많이 사 가려고 한다. 가게에는 $N$ 개의 사탕 묶음이 있고, $i$ 번째 묶음에는 $a_i$ 개의 사탕이 있다. 준석이는 부자라서 사탕 묶음을 원하는 만큼 살 수 있다. 다만 준석이가 사 간 사탕의 총개수가 홀수이면 두 동생이 사탕을 한 개라도 더 가지려고 싸우게 된다. 그래서 준석이는 사탕을 짝수 개만 가져가려고 한다. 준석이가 가져갈 수 있는 사탕의 최대 개수를 구해 보자.

입력

첫째 줄에 사탕 묶음의 개수 $N$ 이 주어진다. ( $1 \leq N \leq 1000$ ) 둘째 줄에 각 사탕 묶음에 담긴 사탕의 개수 $a_1, a_2, \cdots, a_N$ 이 주어진다. ( $1 \leq a_i \leq 1000$ ) 입력으로 주어지는 모든 수는 정수이다.

출력

준석이가 가져갈 수 있는 사탕의 최대 개수를 출력한다.

사탕을 홀수 개로만 가져갈 수 있으면 $0$ 을 출력한다.

예제2

예제 1
입력
```
5
8 3 6 7 5
```
예상 출력
```
26
```
예제 2
입력
```
1
5
```
예상 출력
```
0
```