#include <bits/stdc++.h>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,G;
int gr[5000];
int p[5000];
int c[5000][10000];
int main()
{
    f>>n>>G;
    int i,j;
    for(i=1;i<=n;i++)
        f>>gr[i]>>p[i];
    for(i=1;i<=n;i++)
        for(j=1;j<=G;j++)
        if(gr[i]<=j)
            if(p[i]+c[i-1][j-gr[i]]>c[i-1][j])
                   c[i][j]=p[i]+c[i-1][j-gr[i]];
                else
                    c[i][j]=c[i-1][j];
            else
                c[i][j]=c[i-1][j];
    g<<c[n][G]<<'\n';
    return 0;
}