#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>

#define ull unsigned long long
#define ll long long
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int N,G;
int w[5005],p[5005];
int a[1][10005];

int main()
{
    f>>N>>G;
    FOR(i,1,N)
        f>>w[i]>>p[i];
    FOR(i,1,N)
        ROF(j,G,1)
            if (w[i]<=j) // a[0][j]=profitul maxim pe care-l putem obtine selectand o submultime a primelor i elemente,
                a[0][j]=max(a[0][j],a[0][j-w[i]]+p[i]); // a caror greutate insumata este egala cu cw;
    g<<a[0][G];
    f.close();g.close();
    return 0;
}