#include<iostream>
using namespace std;
const int N=31;
int w[N];
int v;
int n;
int f[20000];
int main(){
    cin>>v>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&w[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=v;j>=w[i];j--){
                f[j]=max(f[j-w[i]]+w[i],f[j]);

        }
    }
    cout<<v-f[v];
}

#include<iostream>
using namespace std;
const int N=110;
int v[N],w[N];
int f[N*10];
int main(){
    int t,n;
    scanf("%d%d",&t,&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&v[i],&w[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=t;j>=v[i];j--){
            f[j]=max(f[j-v[i]]+w[i],f[j]);
        }
    }
    cout<<f[t];
}

#pragma warning(disable:4996)
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
int n, cnt;
int res = 0;
void dfs_c(int state, int level,int a,int c) {
    if (level > 9) return;
    if (c) {
        int b = c * n - c * a;
        if (b < c) return;
            bool flag = true;
            int newstate=state;
            while (b) {
                int g = b % 10;
                if(g==0)
                {
                    flag=false;
                    break;
                }
                if((newstate>>(g-1))&1){
                    flag=false;
                    break;
                }
                newstate|=(1<<(g-1));
                b /= 10;
            }
            if(newstate!=((1<<9)-1))
            flag=false;
            if (flag) {
                res++;
            }

    }
    for (int i = 1; i <= 9; i++) {
        if (((state >> (i - 1)) & 1)) continue;
        dfs_c(state | (1 << (i - 1)), level + 1,a,c*10+i);
    }
}
void dfs_a(int state, int level,int a) {
    if (a >= n) return;
    if (level != 0) {
        dfs_c(state, level,a,0);
    }
    for (int i = 1; i <= 9; i++) {
        if ((state >> (i - 1)) & 1) continue;
        dfs_a(state | 1 << (i - 1),level+1,a*10+i);
    }
}
int main() {
    cin >> n;
    dfs_a(0, 0,0);
    cout << res;
}

#include<iostream>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
int n,m;
struct link{
    int u,level,state;
}stk;
void dfs(int u,int level,int state){
    if(level==m){
        for(int i=1;i<=n;i++){
            if((state>>(i-1))&1)
            cout<<i<<" ";
        }
        cout<<endl;
    }
    for(int i=u;i<=n;i++){
        if((state>>(i-1))&1) continue;
        dfs(i+1,level+1,state|(1<<(i-1)));
    }
}
int main(){
    cin>>n>>m;
    //dfs(1,0,0);
    queue<link> s;
    s.push({1,0,0});
    while(s.size()){
        auto t=s.front();
        s.pop();
        if(t.level==m){
        for(int i=1;i<=n;i++){
            if((t.state>>(i-1))&1)
            cout<<i<<" ";
        }
        cout<<endl;
        }
        for(int i=t.u;i<=n;i++){
            if((t.state>>(i-1))&1) continue;
            s.push({i+1,t.level+1,t.state|(1<<(i-1))});
        }
    }

}

#include<cstring>
#include<iostream>
using namespace std;
const int N=7;
char s[N][N];
int g[N][N];
int n;
int idx[5]={0,0,0,1,-1},idy[5]={0,1,-1,0,0};
void turn(int x,int y){
    for(int i=0;i<5;i++){
        int a=x+idx[i],b=y+idy[i];
        if(a>=0&&a<5&&b>=0&&b<5){
            g[a][b]^=1;
        }
    }
}
int dfs(){
    int ans=0x3f3f3f3f;
    for(int k=0;k<1<<5;k++){
        int res=0;
        int backup[N][N];
        memcpy(backup,g,sizeof g);
        for(int i=0;i<5;i++){
            if((k>>i)&1){
            res++;
            turn(0,i);
            }
        }
        for(int i=0;i<4;i++){
            for(int j=0;j<5;j++){
                if(g[i][j]==0){
                    turn(i+1,j);
                    res++;
                }
            }
        }
        bool flag=true;
        for(int j=0;j<5;j++){
            if(g[4][j]==0) {
                flag=false;
                break;
            }
        }
        if(flag){
            ans=min(ans,res);
        }
        memcpy(g,backup,sizeof g);
    }
    if(ans>6)
    ans=-1;
    return ans;
}
int main(){
    cin>>n;
    while(n--){
        for(int i=0;i<5;i++){
            scanf("%s",s[i]);
        }
        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++){
                g[i][j]=s[i][j]-'0';
            }
        }
       cout<<dfs()<<endl;
    }
}

#include<iostream>
#include<vector>
using namespace std;
int n;
int a[48];
int main(){
    cin>>n;
    a[0]=0,a[1]=1;
    for(int i=2;i<=n-1;i++){
        a[i]=a[i-1]+a[i-2];
    }
   for(int i=0;i<=n-1;i++) printf("%d ",a[i]);
}

#include<iostream>
#include<vector>
using namespace std;
const int N=13;
bool st[N];
int n;
vector<int> q;
void dfs(int u){
    if(u==n){
        for(int i:q){
            printf("%d ",i);
        }
        puts("");
        return;
    }
    for(int i=1;i<=n;i++){
        if(st[i]) continue;
        st[i]=true;
        q.push_back(i);
        dfs(u+1);
        q.pop_back();
        st[i]=false;
    }

}
int main(){
    cin>>n;
    dfs(0);
}

#include<iostream>
using namespace std;
const int N=17;
int n;
int st[N];
void dfs(int u){
    if(u==n+1){
        for(int i=1;i<=n;i++){
            if(st[i]==1) printf("%d ",i);
        }
        printf("\n");
        return ;
    }
    st[u]=1;
    dfs(u+1);
    st[u]=2;
    dfs(u+1);
}
int main(){
    cin>>n;
    dfs(1);
}

/***
 * 参考 最长公共子序列和最长上升子序列的模式
 * 将集合f[i][j] 表示子串a1->ai，b1->bj，以bj为结尾的最长公共子串的长度  
 * 集合可以划分为f[i-1][j] 表示不包含a[i] 包含b[j]的子串长度
 * 考虑包含a[i]的情况 则必须满足条件 a[i]=b[j],
 * 可以由集合 max(f[i-1][1],f[i-1][2])…………一直到j-1构成 f[i][j]为其最大值加1
 ***/
#include<iostream>
using namespace std;
const int N=3010;
int a[N],b[N];
int n;
int f[N][N]; 
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    for(int i=1;i<=n;i++){
        int maxv=1;
        for(int j=1;j<=n;j++){
            f[i][j]=f[i-1][j];
            if(a[i]==b[j]){
            f[i][j]=max(f[i][j],maxv);
            }
            if(a[i]>b[j]){
                maxv=max(maxv,f[i-1][j]+1);
            }
        }

        }

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
    cout << res << endl;
}

#include<iostream>
using namespace std;
const int N=1010;
char a[N],b[N];
int n,m;
int f[N][N];
int main(){
    cin>>n>>m;
    scanf("%s%s",a+1,b+1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if((a[i]==b[j]))
            f[i][j]=max(f[i][j],f[i-1][j-1]+1);
        }
    }
    cout<<f[n][m];
}