SPOJ PARTY - Party Schedule

Write a program which finds this optimal set of parties that offer the most fun. Keep in mind that your budget need not necessarily be reached exactly. Achieve the highest possible fun level, and do not spend more money than is absolutely necessary.

INPUT:
50 10
12 3
15 8
16 9
16 6
10 2
21 9
18 4
12 4
17 8
18 9

50 10
13 8
19 10
16 8
12 9
10 2
12 8
13 5
15 5
11 7
16 2

OUTPUT:

49 26

48 32

#include <bits/stdc++.h>
#define INF 1000000000
#define MOD 1000000007
#define MAXN 1000005
#define ins insert
#define pb push_back
#define mp make_pair
#define sz size
#define rep(i, n) for(int i = 0; i < n; ++i)
#define sd(n) scanf("%d",&n)
#define sll(n) scanf("%I64d",&n)
#define pdn(n) printf("%d\n",n)
#define plln(n) printf("%I64d\n",n)
#define pd(n) printf("%d ",n)
#define nl() printf("\n")
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vi;
typedef vector<vi> vii;
typedef pair<int, int> pii;

int budget, parties;

int fun[101], fee[101];

int dp[101][501];

int solve(int idx, int rembudget)
{
    if(rembudget == 0)
        return 0;
    if(rembudget < 0)
        return 0;
    if(idx < 0)
        return 0;
    if(dp[idx][rembudget] != -1)
        return dp[idx][rembudget];
    int pr1 = 0, pr2 = 0;

    if(rembudget-fee[idx] >= 0)
        pr1 = fun[idx]+solve(idx-1, rembudget-fee[idx]);

    pr2 = solve(idx-1, rembudget);

    return dp[idx][rembudget] = max(pr1, pr2);
}

int main()
{
    while((cin >> budget >> parties) && (budget) && (parties))
    {
        for(int i = 0; i < 101; ++i)
            for(int j = 0; j < 501; ++j)
                dp[i][j] = -1;
        for(int i = 0; i < parties; ++i)
        {
            cin >> fee[i] >> fun[i];
        }
        for(int i = 0; i < 501; ++i)
            solve(parties-1, i);
        int ans = solve(parties-1, budget);
        int currmin = INF;
        for(int i = 0; i < 501; ++i)
        {
            if(dp[parties-1][i] == ans)
            {
                currmin = i;
                break;
            }
        }
        cout << currmin << " " << ans << endl;
    }
    return 0;

}