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

using namespace std;

int n, g, Pmax;
int w[5010], p[5010];
int d[5010][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
    for(int i=1; i<=n; i++)
        for(int c=0; c<=g; c++)
            {
                d[i][c] = d[i-1][c];
                if(w[i]<=c)
                    d[i][c] = max(d[i][c], d[i-1][c-w[i]] + p[i]);
            }
    Pmax=d[n][g];
    printf("%d", Pmax);
    return 0;
}