Pocket Money

Interview

Time limit2sMemory limit512 MB

Summary

Choose banknotes from the wallet so the total is even and as large as possible, using any subset; print NIESTETY if only odd totals are reachable.

Level: Medium4 of 10
Topics: Greedy, Math, Sorting, Array
Solved: No attempts yet

Problem

It is time to hand out pocket money. Mom is delighted with how Bajtek and Bajtolinka cleaned their room. She has decided to give away part of the banknotes from her wallet as pocket money, but in such a way that the children can split the money equally. Mom has no time to exchange money or for unnecessary discussions. If needed, the children will exchange the banknotes they receive at a kiosk themselves.

The official currency of Bajtocja is the bajtalar. The smallest available denomination is 1 bajtalar. Therefore, an amount of b bajtalars can be divided equally between two people exactly when b is even.

Input

The first line of the input contains one integer n (1 ≤ n ≤ 1 000 000), the number of banknotes in mom's wallet. The second line contains n integers a1, a2, . . . , an (1 ≤ ai ≤ 1000), the denominations of those banknotes.

Output

Output the maximum sum of banknote denominations that mom can give away as pocket money so that the children can split the amount they receive equally.

If no positive number of banknotes can be chosen from the wallet so that this condition holds, mom unfortunately has to go to an ATM. In that case, output the word NIESTETY.

Examples2

Example 1
Input
```
5
2 4 3 3 3
```
Expected output
```
12
```
Example 2
Input
```
1
5
```
Expected output
```
NIESTETY
```