#include <stdio.h>
#define MAXV 1000
int dp[MAXV];
 
int main (){
    int N,V;
    scanf("%d %d",&N,&V);
    int a[1000]; //体积
    int b[1000]; //价值
    int i,j;
    for (i=1;i<=N;i++){
        scanf("%d %d",&a[i],&b[i]);
    }
 
    //完全背包：j从小到大
    for(i = 1; i <= N; i++){
        for(j = a[i]; j <= V; j++){
            if(dp[j - a[i]] + b[i] > dp[j]){
                dp[j] = dp[j - a[i]] + b[i];
            }
        }
    }
    printf("%d", dp[V]);
    return 0;
}
 

I2luY2x1ZGUgPHN0ZGlvLmg+CiNkZWZpbmUgTUFYViAxMDAwCmludCBkcFtNQVhWXTsKCmludCBtYWluICgpewogICAgaW50IE4sVjsKICAgIHNjYW5mKCIlZCAlZCIsJk4sJlYpOwogICAgaW50IGFbMTAwMF07IC8v5L2T56evCiAgICBpbnQgYlsxMDAwXTsgLy/ku7flgLwKICAgIGludCBpLGo7CiAgICBmb3IgKGk9MTtpPD1OO2krKyl7CiAgICAgICAgc2NhbmYoIiVkICVkIiwmYVtpXSwmYltpXSk7CiAgICB9CgogICAgLy/lrozlhajog4zljIXvvJpq5LuO5bCP5Yiw5aSnCiAgICBmb3IoaSA9IDE7IGkgPD0gTjsgaSsrKXsKICAgICAgICBmb3IoaiA9IGFbaV07IGogPD0gVjsgaisrKXsKICAgICAgICAgICAgaWYoZHBbaiAtIGFbaV1dICsgYltpXSA+IGRwW2pdKXsKICAgICAgICAgICAgICAgIGRwW2pdID0gZHBbaiAtIGFbaV1dICsgYltpXTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIHByaW50ZigiJWQiLCBkcFtWXSk7CiAgICByZXR1cm4gMDsKfQo=

MyA3CjIgMwo2IDcKMSA0

3 7
2 3
6 7
1 4