L - MaratonIME doesn't like odd numbers

Statements

Estrela is known for defending tolerance time in delay tolerance. When he was attending to his MAC101 classes, there was a 15 minutes tolerance for delays and once he got 19 minutes late to the class. Estrela lost 7 points in his grade because of this even after he tried to explain how big the line for the Hot-Dog truck was. Later that day, he was talking about this situation during a training day for MaratonIME when Yan noticed a something odd: there was a 15 minutes delay tolerance, Estrela was 19 minutes late and lost 7 points. He said: "Estrela, can't you see? These are all odd numbers!".

The observation startled them and they realized that many of MaratonIME's catchphrases had a odd number of alphanumeric characters: "Oh, Fox!", "7", "Wubalubbadubdub", among others. That could not be a coincidence! They also realized that in their own names: Estrela and Yan.

Sena, whose name doesn't fit the observations, wants people to stop worrying about this kind of nonsense and focus on their training but he's busy trying to contain the great ruckus caused by the "7 Theory".

You agree with Sena and believe that if you create a super catchphrase with even length, people won't believe this crazy theory anymore. A super catchphrase is the concatenation of some (possibly none) catchphrases, as an example, "Da Matta is big." (12 alphanumeric characters) and "What a man!" (8 alphanumeric characters) can be used to make the super catchphrase "Da Matta is big. What a man!" (22 alphanumeric characters).

Since MaratonIME has a gigantic amount of catchphrases, you have to make a program that will determine the size of the greatest even length possible for a super catchphrase that is the concatenation of some (possibly none) of MaratonIME catchphrases. Note that if no super catchphrase with even length can be created the answer is 0.

Input

On the first line there will be an integer n, the amount of catchphrases and, on the second line, n integers, the i-th integer, ai, is the amount of alphanumerics on the i-th catchphrase.

Limits

• 1 ≤ n ≤ 105.
• 1 ≤ ai ≤ 104.

Output

Print the largest even size of a super catchphrase.

Examples

Input

3

1 2 4

Output

6

Input

6

4 8 15 16 23 42

Output

108

题目大意及思路：给你几个数相加，判断是不是偶数，是偶数的话，直接输出，不是偶数的话，减去最小的奇数。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void paixu(int a[], int l, int r);
int main()
{
    int n, a[100010], i, sum;
    sum = 0;
    scanf("%d", &n);
    for(i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        sum = sum + a[i];
    }
    paixu(a,1,n);
    if(sum % 2 == 0)
    {
        printf("%d\n", sum);
    }
    else
    {
        for(i = 1; i <= n; i++)
        {
            if(a[i] % 2 != 0)
            {
                break;
            }
        }
        if(i > n)
        {
            printf("0\n");
        }
        else
        {
            printf("%d\n", sum - a[i]);
        }
    }
    return 0;
}
void paixu(int a[], int l, int r)
{
    int i = l, j = r;
    int x = a[i];
    if(i >= j)
    {
        return;
    }
    else
    {
        while(i < j)
        {
            while(i < j && a[j] >= x)
            {
                j--;
            }
            a[i] = a[j];
            while(i < j && a[i] <= x)
            {
                i++;
            }
            a[j] = a[i];
        }
        a[i] = x;
        paixu(a,l,i-1);
        paixu(a,i+1,r);
    }
}