Rucsac_Halloween

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

int n, a[1000], v[10001], G;

bool cmp(int x, int y)
{
    return x < y;
}

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

    sort(a, a + n, cmp);

    for(int i = 0; i < n; i++)
        {
            int s = 0;
            v[a[i]] = 1;
            for(int j = 1; j <= G; j++)
                {
                    if(v[j] && j != a[i])
                    {
                        s = j + a[i];
                        if(s <= G)
                        {
                            if(v[s] == 0)
                                v[s] = v[j] + 1;
                            else
                                v[s] = min(v[s], v[j] + 1);
                        }
                        else
                            break;
                    }
                }
        }
    if(v[G])
        cout<<v[G];
    else
        cout<<"NU";
}