bzoj1606

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<algorithm>
 5 #define re(i,l,r) for(int i=(l);i<=(r);i++)
 6 #define rre(i,r,l) for(int i=(r);i>=(l);i--)
 7 using namespace std;
 8 int c,n,v[5050];
 9 void inin(int &x)
10 {
11     x=0;int f=0;char ch=getchar();
12     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=1;ch=getchar();}
13     while(ch>=‘0‘&&ch<=‘9‘)x*=10,x+=ch-‘0‘,ch=getchar();
14     x=f?-x:x;
15 }
16 int hh[50050];
17 int main()
18 {
19     inin(c),inin(n);
20     re(i,1,n)inin(v[i]);hh[0]=1;
21     re(i,1,n)rre(j,c,v[i])hh[j]+=hh[j-v[i]];
22     while(!hh[c])c--;
23     cout<<c;
24     return 0;
25 }