#include <fstream>
#include <string.h>

#define nMax 5001
#define gMax 10001
#define pii pair<int, int>
#define mkp make_pair

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n, G, Sol;
int dp[gMax];
pii ob[nMax];
void read()
{
    int a, b;
    fin>>n>>G;

    for(int i=1;i<=n;i++)
    {
        fin>>a>>b;
        ob[i]=mkp(a, b);
    }
}
void solve()
{
    memset(dp, -1, sizeof(dp));
    dp[0]=0;

    for(int i=1;i<=n;i++)
    {
        int weight=ob[i].first, price=ob[i].second;
        for(int j=G;j>=weight;j--)
        {
            if(dp[j-weight]!=-1)
            {
                dp[j]=max(dp[j], dp[j-weight]+price);
                Sol=max(Sol, dp[j]);
            }
        }
    }
}
void write()
{
    fout<<Sol;
}
int main()
{
    read();
    solve();
    write();
    return 0;
}