学步园

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

#define MAXN 105

int n,m,k,s;

int C[MAXN];
int W[MAXN];
int dp[MAXN][MAXN];
int ans;
//dp[i][j][k] = max(dp[i-1][j][k],dp[i][j-1][k-C[i]] + W[i]);
//dp[j][k] = max(dp[j][k], dp[j-1][k-C[i]] + W[i]);

int main()
{
    while(cin>>n>>m>>k>>s)
    {
        ans = 0;
        for(int i = 1; i <= k; i++)
        {
            cin>>W[i]>>C[i];
        }
        memset(dp,0,sizeof(dp));
        for(int e = 1; e <= k; e++)
        {
            for(int i = 1; i <= s; i++)
            {
                for(int j = C[e]; j <= m; j++)
                {
                    dp[i][j] = max(dp[i][j], dp[i-1][j-C[e]] + W[e]);  //完全背包
                }
            }
        }
        bool flag = false;
        for(int i = 1; i <= m; i ++)
        {
            if(dp[s][i] >= n)
            {
                flag = true;
                ans = i;
                break;
            }
        }
        if(flag)
            cout<<m-ans<<endl;
        else
            cout<<"-1"<<endl;
    }
    return 0;
}