#include <iostream>
#include <algorithm>
using namespace std;

const int N = 32, M = N * 1e4;
int a[N], n, x, s;
int dp[M];

int main()
{
    cin >> n >> x;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        s += a[i];
    }

    for (int i = 1; i <= n; i ++ )
        for (int j = s - x; j >= a[i]; j -- )
            dp[j] = max(dp[j], dp[j - a[i]] + a[i]);

    cout << s - dp[s - x] << endl;
}

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 22;
int a[N], r[N];

int main()
{
    int n, m;
    cin >> n >> m;
    a[0] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        a[i] *= a[i - 1];
    }

    for (int i = n; i >= 1; i -- ) {
        r[i] = m / a[i - 1];
        m %= a[i - 1];
    }

    for (int i = 1; i <= n; i ++ ) {
        cout << r[i] << " ";
    }
}

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

#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int n, m, dist[N][N], dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
char a[N][N];
PII q[N * N];

void bfs()
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            if (a[i][j] == '1')
            {
                dist[i][j] = 0;
                q[++ tt] = {i, j};
            }

    while (hh <= tt)
    {
        auto t = q[hh ++ ];
        for (int i = 0; i < 4; i ++ )
        {
            int xx = t.x + dx[i], yy = t.y + dy[i];
            if (xx < 1 || xx > n || yy < 1 || yy > m || !dist[xx][yy] || (dist[xx][yy] != -1 && dist[xx][yy] <= dist[t.x][t.y] + 1)) continue;

            q[++ tt] = {xx, yy};
            dist[xx][yy] = dist[t.x][t.y] + 1;
        }
    }
}

int main()
{
    cin >> n >> m;
    memset(dist, -1, sizeof dist);
    for (int i = 1; i <= n; i ++ )
        cin >> a[i] + 1;

    bfs();

    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ )
            cout << dist[i][j] << " ";
        cout << "\n";
    }
}

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

using namespace std;
int n, k;
const int N = 1e5 + 5;
int q[N * 3];
int dist[N];
int d[3] = {-1, 1, 0};

int bfs(int s)
{
    int hh = 0, tt = 0;
    q[0] = s;
    memset(dist, -1, sizeof dist);
    dist[s] = 0;
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i  = 0; i < 3; i ++ )
        {
            int nxt = t + d[i];
            if (!d[i]) nxt <<= 1;
            if (nxt == k) return dist[t] + 1;
            if (nxt > N || nxt < -N || dist[nxt] != -1) continue;

            q[++ tt] = nxt;
            dist[nxt] = dist[t] + 1;
        }
    }
}

int main()
{
    cin >> n >> k;
    if (n == k) cout << 0 << endl;
    else cout << bfs(n) << endl;
}

//这个题意感觉不太清楚，说了和马一样的规则，但是没有马的“拌脚”。。
#include <iostream>
#include <algorithm>
#include <cstring>

#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;

const int N = 155;
int n, m, dx[8] = {-1, -1, -2, -2, 1, 1, 2, 2}, dy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
char a[N][N];
PII q[N * N];
int layer[N][N];
PII st = {-1, -1}, ed = {-1, -1};

void bfs(int sx, int sy)
{
    int cnt = 0;
    q[0] = {sx, sy};
    int hh = 0, tt = 0;
    memset(layer, -1, sizeof layer);
    layer[sx][sy] = 0;
    while (hh <= tt)
    {
        auto t = q[hh ++ ];
        for (int i = 0; i < 8; i ++ )
        {
            int _x = t.x + dx[i], _y = t.y + dy[i];
            // int mid_x = _x + (dx[i] >> 1), mid_y = t.y + (dy[i] >> 1);
            if (_x < 1 || _x > n || _y < 1 || _y > m || layer[_x][_y] != -1 || a[_x][_y] == '*') continue;
            q[++ tt] = {_x, _y};
            layer[_x][_y] = layer[t.x][t.y] + 1;
            if (_x == ed.x && _y == ed.y) return;
        }
    }
}

int main()
{
    cin >> m >> n;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i] + 1;
        for (int j = 1; j <= m; j ++ )
            if (a[i][j] == 'K')
                st = {i, j};
            else if (a[i][j] == 'H')
                ed = {i, j};
    }

    bfs(st.x, st.y);   
    cout << layer[ed.x][ed.y] << endl;
    // for (int i = 1; i <= n; i ++ ) {
    //     for (int j = 1; j <= m; j ++ ) {
    //         cout << layer[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    return 0;
}

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

#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int n, a[N][N], dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
PII q[N * N], pre[N][N];

void bfs(int sx, int sy)
{
    int hh = 0, tt = 0;
    q[0] = {sx, sy};
    memset(pre, -1, sizeof pre);
    pre[sx][sy] = {0, 0};
    while (hh <= tt) 
    {
        auto t = q[hh ++ ];
        for (int i = 0; i < 4; i ++ )
        {
            int x = t.x + dx[i], y = t.y + dy[i];
            if (x >= n || x < 0 || y >= n || y < 0 || pre[x][y].x != -1 || a[x][y]) continue;

            q[++ tt] = {x, y};
            pre[x][y] = {t.x, t.y};
        }
    }
}

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


    bfs(n - 1, n - 1);

    PII now(0, 0);

    while (true) {
        cout << now.x << " " << now.y << endl;
        if (now.x == n - 1 && now.y == n - 1) break;
        now = pre[now.x][now.y];
    }

    return 0;
}

// 调了半天的搜索......
#include <iostream>
#include <algorithm>
#include <cstring>
#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int a[N][N], n;
PII q[N * N];
bool st[N][N];

int bfs(int sx, int sy)
{
    int hh = 0, tt = 0;
    q[0] = {sx, sy};
    st[sx][sy] = true;
    int flag = 0;
    while (hh <= tt) 
    {
        auto t = q[hh ++];

        for (int i = t.x - 1; i <= t.x + 1; i ++ )
            for (int j = t.y - 1; j <= t.y + 1; j ++ )
            {
                if (i == t.x && j == t.y) continue;
                if (i < 1 || i > n || j < 1 || j > n) continue;
                if (a[i][j] != a[t.x][t.y]) {
                    if (!flag)
                        flag = a[t.x][t.y] > a[i][j] ? 1 : -1;
                    else if (flag == -2) continue;
                    else if (flag * (a[t.x][t.y] - a[i][j]) < 0) flag = -2;
                }
                else if (!st[i][j]) {
                    q[++ tt] = {i, j};
                    st[i][j] = true;
                }
            }
    }
    if (tt == n * n - 1 && !flag) flag = 2;
    if (flag == -2) flag = 0;
    return flag;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            cin >> a[i][j];

    int top = 0, bottom = 0, cnt = 0;        
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (!st[i][j])
            {
                cnt = bfs(i, j);
                // cout << i << ", " << j << ", val: " << cnt << endl;
                if (cnt == 1)
                    top ++;
                else if (cnt == 2) {
                    top ++;
                    bottom ++;
                }
                else if (cnt < 0) bottom ++;
            }

    cout << top << " " << bottom << endl;
}

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define x first
#define y second

typedef pair <int, int> PII;
const int N = 55;
int m, n, a[N][N];
PII q[N * N];
bool st[N][N];
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};

int bfs(int sx, int sy) {
    int hh = 0, tt = 0;
    q[0] = {sx, sy};
    st[sx][sy] = true;
    while (hh <= tt) {
        auto t = q[hh ++ ];
        for (int i = 0; i < 4; i ++ )
        {
            int x = t.x + dx[i], y = t.y + dy[i];
            if (st[x][y] || x < 1 || x > n || y < 1 || y > m) continue;
            if (a[t.x][t.y] >> i & 1) continue;

            q[++ tt] = {x, y};
            st[x][y] = true;
        }
    }
    return tt + 1;
}


int main()
{
    cin >> n >> m;
    int cnt = 0;
    int ans = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            cin >> a[i][j];
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            if (!st[i][j]) {
                ans = max(ans, bfs(i, j));
                cnt ++;
            }
    cout << cnt << "\n" << ans << endl;
}

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

#define x first
#define y second

using namespace std;

typedef pair <int, int> PII;
const int N = 1010;
char a[N][N];
PII q[N * N];
int n, m;
bool st[N][N];

void bfs(int xx, int yy)
{
    int hh = 0, tt = -1;
    q[0] = {xx, yy};
    st[xx][yy] = true;
    tt ++;
    while (hh <= tt) {
        auto t = q[hh ++];
        for (int i = t.x - 1; i <= t.x + 1; i ++ )
            for (int j = t.y - 1; j <= t.y + 1; j ++ )
            {
                if (i == xx && yy == j) continue;
                if (st[i][j] || i < 1 || i > n || j < 1 || j > m) continue;
                if (a[i][j] == '.') continue;

                q[++ tt] = {i, j};
                st[i][j] = true;
            }
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        cin >> a[i] + 1;

    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            if (a[i][j] == 'W' && !st[i][j]) {
                bfs(i, j);
                cnt ++;
            }
        }

    cout << cnt << endl;
}

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

using namespace std;
const int N = 110, M = 25e3 + 5;
int T, n, a[N], f[M];

int main()
{
    cin >> T;
    while (T -- ) {
        cin >> n;
        for (int i = 1; i <= n; i ++ ) {
            cin >> a[i];
        }

        sort(a + 1, a + n + 1);

        int maxv = a[n];

        int num = 0;
        memset(f, 0, sizeof f);
        f[0] = 1;
        for (int i = 1; i <= n; i ++ ) {
             if (!f[a[i]]) num ++;
            for (int j = a[i]; j <= maxv; j ++ ) {
                f[j] |= f[j - a[i]];
            }
        }

        cout << num << endl;
    }
}