学步园

思路：基础的0/1背包模型

//212K   
250MS
#include <stdio.h>
#include <string.h>
#define M 13500
int max (int a,int b)
{
    return a
> b? a: b;
}
int main ()
{
    int
dp[M];
    int
n,m,i,w,d;
    while
(~scanf ("%d%d",&n,&m))
    {
       
memset (dp,0,sizeof (dp));
       
for (i = 0;i < n;i ++)
       
{
           
scanf ("%d%d",&w,&d);
           
for (int j = m;j >= w;j --)
               
dp[j] = max (dp[j],dp[j-w] + d);
       
}
       
printf ("%d\n",dp[m]);
    }
}