#include <bits/stdc++.h>

using namespace std;

const int NMAX = 5003;
const int GMAX = 10003;

int n,g;
int dp[2][GMAX];

struct elem{
    int w,val;
};

elem v[NMAX];

int main(){
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    scanf("%d %d",&n,&g);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &v[i].w, &v[i].val);
    }
    for(int i=1;i<=n;i++){
        int lin = i%2;
        for (int j = 0; j <= g; j++) {// j este greutatea
            dp[lin][j] = dp[lin ^ 1][j];
            if (j >= v[i].w)dp[lin][j] = max(dp[lin][j], dp[lin ^ 1][j - v[i].w] + v[i].val);
        }
    }
    printf("%d\n",dp[n%2][g]);

    return 0;
}