#include<fstream>
#define In "rucsac.in"
#define Out "rucsac.out"
#define N 5004
#define M 10004
#define max(a,b) ( ((a)>(b)) ?a :b)
a[l][j] = max(a[l][j] ,a[l1][j-w[i]] + p[i]);
using namespace std;
int w[N],p[N],n,g;
int a[2][M];
ifstream fin(In);
ofstream fout(Out);
void Citire()
{
    fin>>n>>g;
    for(int i=1;i<=n;i++)
        fin>>w[i]>>p[i];
    fin.close();
}
a[l][j] = max(a[l][j] ,a[l1][j-w[i]] + p[i]);
void Dinamic()
{
    int j, i,l = 1, l1= 0;
    for(i = 1;i <= n;i++)
    {
        for(j = 0;j <= g;j++)
        {
            a[l][j] = a[l1][j];
            if(w[i]<=j)
            {
                a[l][j] = max(a[l][j] ,a[l1][j-w[i]] + p[i]);
            }
        }
        l ^= 1;
        l1 ^= 1;
    }
    fout<<a[l1][g]<<"\n";
}

int main()
{
    Citire();
    Dinamic();
    return 0;
}