Mika is a very rich guy. He has  bags of apples. Each bag contains a positive integer number of apples, the bag with number  containing  apples. Mika decided that the time has come to sell some of his bags. When selling a bag, Mika is automatically selling each apple inside the bag, but he can't take an apple out of the bag and sell it separately. To make this more interesting, Mika added yet another extra condition: he wants the total number of sold apples to be divisible by .

So Mika is wondering what is the maximum number of apples that can be sold? Help him calculate that number.

Input Format

The first line contains integer  (), the number of Mika's bags of apples.

The second line contains  numbers  (), where  is the number of apples in the bag ().

Output Format

In a single line, print the largest total number of apples which can be sold.

Sample Input 1

4
2 2 1 2
Sample Output 1

6
Sample Input 2

5
3 6 9 9 3
Sample Output 2

30
Explanation

In the first sample, the best option is to sell three bags, each containing  apples. In total, Mika will sell  apples.

In the second sample, the number of apples in every bag is divisible by . So, the total sum of apples is divisible by and Mika can sell all his bags.

CODE:

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1010;
int n, s, m, a[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), s += a[i];
    if (!(s % 3)) m = s;
    for (int i = 1; i <= n; i++) if (!((s - a[i]) % 3)) m = max(m, s - a[i]);
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++) if (!((s - a[i] - a[j]) % 3)) m = max(m, s - a[i] - a[j]);
    printf("%d", m);
    return 0;
}