#include<iostream>
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<algorithm>
#define INF (1 << 30)
#define pb push_back
#define mkp make_pair
#define pii pair<int, int>
#define ll long long
#define nxt (*it)
#define type int
#define FORir(i,a,b)\
   for(int i=a; i>=b; --i)
#define FORi(i,a,b)\
   for(int i=a; i<=b; ++i)
#define FORr(g)\
   for(vector<type>::reverse_iterator it=g.rbegin(); it!=g.rend(); ++it)
#define FOR(g)\
   for(vector<type>::iterator it=g.begin(); it!=g.end(); ++it)
#define infile "rucsac.in"
#define outfile "rucsac.out"
#define gMax 10005
#define nMax 5005
using namespace std;

int DP[gMax], g[nMax], p[nMax];

int N, G;

void read(){
    ifstream f(infile);

    f >> N >> G;

    FORi(i,1,N)
       f >> g[i] >> p[i];

    f.close();
}

void solve(){
    FORi(i,1,N)
       FORir(S,G,1)
          if(S - g[i] >= 0 && (DP[S - g[i]] || S - g[i] == 0))
             DP[S] = max(DP[S], DP[S - g[i]] + p[i]);
}

void print(){
    ofstream g(outfile);

    g << DP[G] << '\n';

    g.close();
}

int main(){
    read();
    solve();
    print();

    return 0;
}