腾讯马拉松-减肥记I-hdu4508

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define max(x,y) x>y?x:y;
int v[100001];
int w[100001];
int dp[100001];
int main()
{
    int n,m;
   // freopen("input.txt","r",stdin);
    while(scanf("%d",&n)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        for(int i=1; i<=n; i++)
            scanf("%d%d",&v[i],&w[i]);
        scanf("%d",&m);
        for(int i=1; i<=n; i++)
            for(int j=w[i]; j<=m; j++)
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        printf("%d\n",dp[m]);
    }
    return 0;
}