4 6
1 42 63 122 7




//  poj 3624   标准的01背包   优化的一位数组
#include <iostream>
#include <string.h>
using namespace std;
int w[3500],v[3500],dp[13000];
int main ()
{   int n,m,i,j;
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++) scanf("%d%d",&w[i],&v[i]);
    memset(dp,0,sizeof(dp));
    for (i=1;i<=n;i++)
        for (j=m;j>=w[i];j--)
            if (dp[j]<dp[j-w[i]]+v[i])   dp[j]=dp[j-w[i]]+v[i];
    printf("%d\n",dp[m]);
    return 0;
}





//  poj 3624   标准的01背包   优化的一位数组
#include <stdio.h>
int main()
{
    int n, v, i, j, ans, c[3403], w[3403], f[12881];
    scanf("%d %d", &n, &v);
    for (i = 1; i <= n; i++)      scanf("%d %d", &c[i], &w[i]);
    for (i = 0; i <= v; i++)      f[i] = 0;
    for (i = 1; i <= n; i++)
        for (j = v; j >= c[i]; j--)
            if (f[j - c[i]] + w[i] > f[j])  f[j] = f[j - c[i]] + w[i];
    ans = 0;
    for (i = 1; i <= v; i++)
        if (f[i] > ans)     ans = f[i];
    printf("%d\n", ans);
    return 0;
}