学步园

#include <stdio.h>
#include <string.h>
#define M 105

int  f[M][M],a[M],b[M];
int n,m,k,s;
int max (int a ,int b)
{
    return a
> b ? a : b;
}
int  dp ()
{
    for (int rm
= 1; rm <= m; rm ++)
       
for (int sm = 1; sm <= s; sm ++)
       
{
           
for (int i = 1; i <= k; i ++)
               
if (rm >= b[i])
                   
f[rm][sm] = max (f[rm][sm],f[rm-b[i]][sm-1] + a[i]);
           
if (f[rm][sm] >=
n)    
//经验值大于所要求的，返回退出
               
return m - rm;
       
}
    return
-1;
}
int main ()
{

    while
(~scanf("%d%d%d%d",&n,&m,&k,&s))

    {
       
memset (f,0,sizeof(f));
       
for (int i = 1; i <= k; i ++)
           
scanf ("%d%d",&a[i],&b[i]);
       
printf ("%d\n",dp());
    }
    return
0;
}