1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #define rep(i,l,r) for(int i=l;i<=r;++i) 5 using namespace std; 6 int n,m,t[20],v[20],two[20],all,f[1023333],ti[1023333],w[1023333]; 7 int main(){ 8     scanf("%d%d",&m,&n); 9     rep(i,1,n) scanf("%d%d",&t[i],&v[i]);10     two[0]=1;rep(i,1,20) two[i]=two[i-1]*2;11     all=two[n]-1;12     memset(f,60,sizeof f); f[0]=0;13     rep(i,1,all) rep(j,1,n) if(two[j-1]&i) w[i]+=v[j],ti[i]=max(ti[i],t[j]);14     rep(S,1,all) for(int x=S;x;x=(x-1)&S) if(w[x]<=m) f[S]=min(f[S],f[S-x]+ti[x]);15     printf("%d\n",f[all]);16 }