#include<bits/stdc++.h>
using namespace std;
const int N=40;
int t[N],v[N];
int f[20010];//f[j]表示容量为j的背包最多装多少体积
int main(){
    int T,n;
    cin>>T>>n;
    for(int i=1;i<=n;i++){
        cin>>v[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=T;j>=v[i];j--){
            f[j]=max(f[j],f[j-v[i]]+v[i]);
        }
    }
    cout<<T-f[T]<<endl;
}

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int t[N],v[N];
int f[1010];
int main(){
    int T,n;
    cin>>T>>n;
    for(int i=1;i<=n;i++){
        cin>>t[i]>>v[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=T;j>=t[i];j--){
            f[j]=max(f[j],f[j-t[i]]+v[i]);
        }
    }
    cout<<f[T]<<endl;
}

#include<bits/stdc++.h>
#define mod  1000000009
using namespace std;
const int N=100010;
typedef long long LL;
int a[N];
int n,k;
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    sort(a,a+n);
    LL res=1;
    if(n==k){ //全部选
        for(int i=0;i<n;i++){
          res=(res*a[i])%mod;
        }
        cout<<res%mod;
        return 0;
    }
    //数组里面都是负数
    if(a[n-1]<0){ //分奇数偶数-8 -3 -2||-4 -3 -2 -1
          if(k%2==1){
            for(int i=n-1;i>=n-k;i--){//奇数的话相乘肯定为负数，那么从后往前绝对值比较小 
                res=(res*a[i])%mod;
            }
          }
          else{
             for(int i=0;i<k;i++){
                res=(res*a[i])%mod;
            } 
          }
            cout<<res<<endl;
            return 0;
        }


        //数组里面有正数
    int l=0,r=n-1;
    if(k%2==1){//k是奇数
        res=a[r--];//取一个数k为偶数
        k--;//注意减掉
    }
    while(k){
        LL x=(LL)a[l]*a[l+1],y=(LL)a[r]*a[r-1];//因为x，y可能爆int
        if(x>y){
            res=x%mod*res%mod;
            l+=2;
        }
        else{
            res=y%mod*res%mod;
            r-=2;
        }
        k-=2;
    }
    cout<<res<<endl;
    return 0;
}

#include<bits/stdc++.h>
#define mod  1000000009
using namespace std;
const int N=100010;
typedef long long LL;
int a[N];
int n,k;
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    sort(a,a+n);
    LL res=1;
    if(n==k){ //全部选
        for(int i=0;i<n;i++){
          res=(res*a[i])%mod;
        }
        cout<<res%mod;
        return 0;
    }
    //数组里面都是负数
    if(a[n-1]<0){ //分奇数偶数-8 -3 -2||-4 -3 -2 -1
          if(k%2==1){
            for(int i=n-1;i>=n-k;i--){
                res=(res*a[i])%mod;
            }
          }
          else{
             for(int i=0;i<k;i++){
                res=(res*a[i])%mod;
            } 
          }
            cout<<res<<endl;
            return 0;
        }


        //数组里面有正数
    int l=0,r=n-1;
    if(k%2==1){//k是奇数
        res=a[r--];//取一个数k为偶数
        k--;//注意减掉
    }
    while(k){
        LL x=(LL)a[l]*a[l+1],y=(LL)a[r]*a[r-1];
        if(x>y){
            res=x%mod*res%mod;
            l+=2;
        }
        else{
            res=y%mod*res%mod;
            r-=2;
        }
        k-=2;
    }
    cout<<res<<endl;
    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 5010;

int n;
PII city[N];
int f[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d%d", &city[i].first, &city[i].second);
    sort(city, city + n);

    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        f[i] = 1;
        for (int j = 0; j < i; j ++ )
            if(city[j].second<city[i].second)
              f[i]=max(f[i],f[j]+1);
        res = max(res, f[i]);
    }

    printf("%d\n", res);

    return 0;
}

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int N = 25;

int n, m;
//需要的每种维生素量，每一种方案，每种方案求和的结果
int need[N], s[N][N], sum[N];
vector<int> res;

int main()
{
    cin >> m;
    for(int i = 0; i < m; i++) cin >> need[i];

    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> s[i][j];

    //枚举每一种方案
    for(int i = 0; i < 1 << n; i++)
    {
        memset(sum, 0, sizeof sum);

        vector<int> t;
        //检查是否选择了这一行
        for(int j = 0; j < n; j++)
        {
            if(i >> j & 1)
            {
                t.push_back(j);
                for(int k = 0; k < m; k++)
                    sum[k] += s[j][k];
            }
        }

        //检查是否满足要求
        bool flag = true;
        for(int j = 0; j < m; j++)
            if(sum[j] < need[j])
            {
                flag = false;
                break;
            }

        if(flag)
            if(res.empty() || res.size() > t.size() || (res.size() == t.size() && res > t))//最少数量
                res = t;
    }

    cout << res.size() << ' ';
    for(auto t : res) cout << t + 1 << ' ';

    return 0;
}

#include<cstdio>
#include<algorithm>
#include<vector>

using namespace std;

struct Node{
    int up, down;
    bool operator< (const struct Node &T) const {
        return up * T.down < T.up * down;
    }
};

vector<Node> v;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int main()
{
    int n;
    scanf("%d", &n);
    for(int down = 2; down <= n; down ++)
        for(int up = 1; up <= down; up ++)
            if(gcd(up, down) == 1)  v.push_back({up, down});
    printf("0/1\n");
    sort(v.begin(), v.end());//按照值从小到大排序
    for(auto &p : v)  printf("%d/%d\n", p.up, p.down);
    printf("1/1\n");
    return 0;
}

#include<cstdio>
#include<algorithm>
#include<vector>

using namespace std;

struct Node{
    int up, down;
    bool operator< (const struct Node &T) const {
        return up * T.down < T.up * down;
    }
};

vector<Node> v;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int main()
{
    int n;
    scanf("%d", &n);
    for(int down = 1; down <= n; down ++)
        for(int up = 0; up <= down; up ++)
            if(gcd(up, down) == 1)  v.push_back({up, down});

    sort(v.begin(), v.end());
    for(auto &p : v)  printf("%d/%d\n", p.up, p.down);
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10000;

int n;
int ans[N], top = N;
int path[N];
string state, target;

void dfs(int p, int k)
{
    if (k >= top) return;
    if (state == target) //第一次更新就是最小字典序
    {
        memcpy(ans, path, k * 4);
        top = k;
        return;
    }
    if (p - 2 >= 0 && state[p - 2] == 'W' && state[p - 1] == 'B')//wb_
    {
        path[k] = p - 2;
        swap(state[p - 2], state[p]);
        dfs(p - 2, k + 1);
        swap(state[p - 2], state[p]);
    }
    if (p - 1 >= 0 && state[p - 1] == 'W')//w_
    {
        path[k] = p - 1;
        swap(state[p - 1], state[p]);
        dfs(p - 1, k + 1);
        swap(state[p - 1], state[p]);
    }
    if (p + 1 <= n * 2 && state[p + 1] == 'B')//_b
    {
        path[k] = p + 1;
        swap(state[p + 1], state[p]);
        dfs(p + 1, k + 1);
        swap(state[p + 1], state[p]);
    }
    if (p + 2 <= n * 2 && state[p + 2] == 'B' && state[p + 1] == 'W')//_wb
    {
        path[k] = p + 2;
        swap(state[p + 2], state[p]);
        dfs(p + 2, k + 1);
        swap(state[p + 2], state[p]);
    }
}

int main()
{
    cin >> n;
    state = string(n, 'W') + ' ' + string(n, 'B');
    target = state;
    reverse(target.begin(), target.end());
    dfs(n, 0);//第一个空格的位置在n位置上

    for (int i = 0; i < top; i ++ )
    {
        cout << ans[i] + 1;
        if ((i + 1) % 20 == 0) cout << endl;
        else cout << ' ';
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 55, M = N * N;

int n, m;
int g[N][N];
int p[M], sz[M];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> m >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            cin >> g[i][j];

    for (int i = 0; i < n * m; i ++ )//并查集初始化
    {
        p[i] = i;
        sz[i] = 1;
    }

    int dx[2] = {-1, 0}, dy[2] = {0, 1}, dw[2] = {2, 4};
    int cnt = n * m, max_area = 1;//房间最小是1
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            for (int u = 0; u < 2; u ++ )
                if (!(g[i][j] & dw[u]))//可以往这个方向走
                {
                    int x = i + dx[u], y = j + dy[u];
                    if (x < 0 || x >= n || y < 0 || y >= m) continue;
                    int a = i * m + j, b = x * m + y;
                    a = find(a), b = find(b);
                    if (a != b)
                    {
                        cnt -- ;
                        sz[b] += sz[a];
                        p[a] = b;
                        max_area = max(max_area, sz[b]);
                    }
                }

    cout << cnt << endl << max_area << endl;
    max_area = 0;
    int rx, ry, rw;

    for (int j = 0; j < m; j ++ )
        for (int i = n - 1; i >= 0; i -- )
            for (int u = 0; u < 2; u ++ )
                if (g[i][j] & dw[u])//这个方向有墙壁
                {
                    int x = i + dx[u], y = j + dy[u];
                    if (x < 0 || x >= n || y < 0 || y >= m) continue;
                    int a = i * m + j, b = x * m + y;
                    a = find(a), b = find(b);
                    if (a != b)
                    {
                        int area = sz[a] + sz[b];
                        if (area > max_area)
                        {
                            max_area = area;
                            rx = i, ry = j, rw = u;
                        }
                    }
                }

    cout << max_area << endl;
    cout << rx + 1 << ' ' << ry + 1 << ' ' << (rw ? 'E': 'N') << endl;

    return 0;
}