Description

It's yet another festival season in Gensokyo. Little girl Alice planned to pick mushrooms in five mountains. She brought five bags with her and used different bags to collect mushrooms from different mountains. Each bag has a capacity of 2012 grams. Alice has finished picking mushrooms in 0 ≤ n ≤ 5 mountains. In the i-th mountain, she picked 0 ≤ wi ≤ 2012 grams of mushrooms. Now she is moving forward to the remained mountains. After finishing picking mushrooms in all the five mountains, she want to bring as much mushrooms as possible home to cook a delicious soup.
Alice lives in the forest of magic. At the entry of the forest of magic, live three mischievous fairies, Sunny, Lunar and Star. On Alice's way back home, to enter the forest, she must give them exactly three bags of mushrooms whose total weight must be of integral kilograms. If she cannot do so, she must leave all the five bags and enter the forest with no mushrooms.
Somewhere in the forest of magic near Alice's house, lives a magician, Marisa. Marisa will steal 1 kilogram of mushrooms repeatedly from Alice until she has no more than 1 kilogram mushrooms in total. So when Alice gets home, what's the maximum possible amount of mushrooms Alice has? Remember that our common sense doesn't always hold in Gensokyo. People in Gensokyo believe that 1 kilogram is equal to 1024 grams.

Input

There are about 8192 test cases. Proceed to the end of file.
The first line of each test case contains an integer 0 ≤ n ≤ 5, the number of mountains where Alice has picked mushrooms. The second line contains n integers 0 ≤ wi ≤ 2012, the amount of mushrooms picked in each mountain.

Output

For each test case, output the maximum possible amount of mushrooms Alice can bring home, modulo 20121014 (this is NOT a prime).

Sample Input

1
9
4
512 512 512 512
5
100 200 300 400 500
5
208 308 508 708 1108

Sample Output

1024
1024
0
792

Hint

In the second sample, if Alice doesn't pick any mushrooms from the 5-th mountain. She can give (512+512+0) =1024 grams of mushrooms to Sunny, Lunar and Star. Marisa won't steal any mushrooms from her as she has exactly 1 kilogram of mushrooms in total.
In the third sample, there are no three bags whose total weight is of integral kilograms. So Alice must leave all the five bags and enter the forest with no mushrooms.
In the last sample:
1.Giving Sunny, Lunar and Star: (208+308+508)=1024
2.Stolen by Marisa: ((708+1108)-1024)=792

Source

2012 Asia ChangChun Regional Contest

题意：

爱丽丝拿着五个容量为1024g（1公斤）的袋子去五座山上采蘑菇，不同山上的蘑菇放到不同袋子里。采完5座山上的蘑菇后要拿出3个袋子送给仙女们，这三个袋子里的蘑菇重量是1公斤的整数倍，然后女巫会收走爱丽丝剩余的蘑菇，每次1公斤，直到爱丽丝的蘑菇总重量不超过1公斤。目前爱丽丝已经采完了（划重点！！）n座山上的蘑菇，问爱丽丝最多能剩下多少蘑菇？

分情况讨论：

n<=3    怎么样都可以剩下1024g

n==4   如果现在有三个袋子可以组成1024的整数倍，那么最后一个空袋子就可以和另一个袋子拼成1024，剩余的蘑菇同样为                  1024g

          如果这四个袋子没有3个可以组成1024的整数倍，那么最后一个袋子要用来和其中两个拼凑成1024的整数倍后，把这三个             袋子送给仙女，两层循环找剩余量的最大值（不断减1024后再取max）就是答案。

n==5   如果没有3个袋子可以组成1024的整数倍，答案是0；如果存在，两层循环找剩余量的最大值（不断减1024后再取max）             就是答案。

#include <bits/stdc++.h>
using namespace std;
int a[10];
const int mod=20121014;
const int inf=0x3f3f3f3f;
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(a,0,sizeof(a));
        int sum=0;
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
        }
        int ans=0;
        if(n<=3&&n>=0)
            ans=1024;
        else if(n==4)
        {
            bool flag=0;
            for(int i=1; i<=n; i++)
            {
                for(int j=i+1; j<=n; j++)
                {
                    for(int k=j+1; k<=n; k++)
                    {
//                        if(i==j||i==k||j==k)
//                            continue;
                        if((a[i]+a[j]+a[k])%1024==0)
                        {
                            ans=1024;
                            flag=1;
//                            break;
                        }
                    }
                }
            }
            if(!flag)
            {
                int minn=inf;
                for(int i=1; i<=n; i++)
                {
                    for(int j=i+1; j<=n; j++)
                    {
                        int tmp=a[i]+a[j];
                        while(tmp>1024)
                            tmp-=1024;
                        ans=max(tmp,ans);
                    }
                }
            }
        }
        else if(n==5)
        {
            bool flag=0;
            for(int i=1; i<=n; i++)
            {
                for(int j=i+1; j<=n; j++)
                {
                    if((sum-a[i]-a[j])%1024==0)
                    {
                        flag=1;
                        int tmp=a[i]+a[j];
                        while(tmp>1024)
                            tmp-=1024;
                        ans=max(tmp,ans);
                    }
                }
            }
            if(!flag)
                ans=0;
        }
        cout<<ans<<'\n';
    }
    return 0;
}