#include <bits/stdc++.h>
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

const int NMAX = 5e3;
const int GMAX = 1e4;
const int INF = 0x3F3F3F3F;

int n,g;
int G[NMAX + 1], P[NMAX + 1];
int m[NMAX + 1][GMAX + 1];

void initializare(){
    for(int i = 1;i<=n;++i)
        for(int j = 1;j<=g;++j)
            m[i][j] = INF;
}

int rucsac(int i, int g){
    if(i == 0)
        return 0;
    if(m[i][g] != INF)
        return m[i][g];
    int skip_obj = rucsac(i - 1, g);
    int get_obj = 0;
    if(G[i] <= g)
        get_obj = P[i] + rucsac(i - 1, g - G[i]);
    int ans = max(get_obj, skip_obj);
    m[i][g] = ans;
    return m[i][g];
}

int main(){

    fin >> n >> g;
    for(int i = 1;i<=n;++i)
        fin >> G[i] >> P[i];
    initializare();
    fout << rucsac(n,g);
    return 0;
}