#include <stdio.h>
#include <algorithm>

using namespace std;

int n, g, Pmax;
int w[5010], p[5010];
int d[2][10010];
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", &w[i], &p[i]);
    //d[i][c] = profitul maxim cu primele i elemente cu suma greutatilor c
    int l=0;
    for(int i = 1; i <= n; ++i, l = 1 - l)
        for(int c = 0; c <= g; ++c)
            {
                d[1-l][c] = d[l][c];
                if(w[i] <= c)
                    d[1-l][c] = max(d[1-l][c], d[l][c - w[i]] + p[i]);
            }
    Pmax=d[l][g];
    printf("%d", Pmax);
    return 0;
}