party.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
    ll mw,n,i,j,val,wt;
    cin>>mw>>n;
    while(mw!=0&&n!=0){
        
            ll v[n],w[n];
            for(i=0;i<n;i++){
                cin>>wt>>val;
                v[i]=val;
                w[i]=wt;
            }
            ll** dp=new ll*[n+1];
        
            for(i=0;i<=n;i++)
                dp[i]=new ll[mw+1];
        
            for(i=0;i<=mw;i++)
                dp[0][i]=0;
        
            for(i=1;i<=n;i++)
                dp[i][0]=0;
            
            for(i=1;i<=n;i++){
                for(j=1;j<=mw;j++){
                    dp[i][j] = dp[i-1][j];
			        if(w[i-1] <= j) dp[i][j]=max(dp[i][j],v[i-1] + dp[i-1][j-w[i-1]]);
                }
            }
        
        for(i=0;i<=mw;i++)
            if(dp[n][i]==dp[n][mw])
                break;
        
        ll ans = dp[n][mw];
        for(j=0;j<=n;j++){
            delete []dp[j];
        }
        delete []dp;
        cout<<i<<" "<<ans<<endl;
        cin>>mw>>n;
    }
    return 0;
}