1828: The Stamps

4^th JOJ Cup Online VContest Problem

An envelop can be pasted at most N(1<=N<=100) pieces of stamps. Now you have M(1<=M<=100) different kinds of stamps, each of which has a unique value V(1<=V<=255). You can assume that you have infinite number of pieces of each kind of stamp. You are to write a program to calculate the maximum value MAX, where each value between 1 to MAX is available. For example, when N=4, M=2 and the stamps have value 1 or 4, you can get the value 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13 and 16. So the answer is 10.

Input

The input consists of several test cases, each of which has the following format:

N M
V1 V2...VM

where V1...VM describe the values of all M kinds.

Output

For each test case, print MAX in a single line.

Sample Input

4 2
1 4
5 3
1 3 9

Sample Output

10
25

#include<stdio.h>
#include<string.h>
int a[100000],flag[100000];
int main()
{
 int n,m,i,j;
 while(scanf("%d%d",&n,&m)==2)
 {
  memset(flag,0,sizeof(flag));
  for(i=0;i<m;i++)
  {
   scanf("%d",&a[i]);
   flag[a[i]]=true;
  }
  int begin=0,end,num=m;
  n--;
  while(n--)
  {
   end=num;
   for(i=0;i<m;i++)
   {
    for(j=begin;j<end;j++)
    {
     int t=a[i]+a[j];
     if(!flag[t])
     {
     a[num++]=t;
     flag[t]=true;
     }
    }
   }
   begin=end;
  }
  for(i=1;flag[i]==true;i++);
     printf("%d/n",i-1);
 }
 return 0;
}