#include <bits/stdc++.h>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int a[5005],b[5005];
int n,i,j;
int g;
int dp[10005];

int mymax(int a, int b)
{
    return (a>b?a:b);
}

signed main()
{
    fin>>n>>g;
    for(i=1;i<=n;i++)
        fin>>a[i]>>b[i];
    for(i=1;i<=n;i++)
    {
        for(j=g-a[i];j>=0;j--)
            dp[j+a[i]]=mymax(dp[j+a[i]],dp[j]+b[i]);
    }
    for(i=1;i<=g;i++)
        dp[i]=mymax(dp[i],dp[i-1]);
    fout<<dp[g]<<'\n';
    return 0;
}