UVa 11517 Exact Change Solution

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

int main(){
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--){
        int sum,n;
        cin>>sum>>n;
        vector<int> coin(n+1);
        for(int i=1;i<=n;i++)
            cin>>coin[i];
        int money,index;
        vector<vector<int> > d(102,vector<int>(20001,10001));
        for(int i=0;i<n;i++)
            d[i][0]=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<20001;j++){
                if(coin[i]<=j)
                    d[i][j]=min(d[i-1][j],1+d[i-1][j-coin[i]]);
                else
                    d[i][j]=d[i-1][j];
            }
        }
        for(int i=sum;i<20001;i++){
                index=d[n][i];
                money=i;
                if(index!=10001)
                break;
        }
        cout<<money<<' '<<index<<endl;

    }
    return 0;
}