#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 5005;
const int MAXG = 10005;
int N, G, l;
int sol[MAXN][MAXG];
int dim[MAXN], p[MAXN];



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", &dim[i], &p[i]);
    l = 0;
    for(int i = 1; i <= N; ++i) {
        l = 1 - l;
        for(int j = 0; j <= G; ++j) {
            if(j >= dim[i])
                sol[l][j] = max(sol[1 - l][j], sol[1 - l][j - dim[i]] + p[i]);
            else sol[l][j] = sol[1 - l][j];
        }
    }
    printf("%d\n", sol[l][G]);
    
}