#include <bits/stdc++.h>

using namespace std;

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

int n,G;
int dp[3][10005],v[5005],g[5005];

int main()
{
    int i,j,l1,l2,maxim;
    fin>>n>>G;
    for(i=1;i<=n;i++)
        fin>>g[i]>>v[i];

    l1=0;l2=1;

    dp[l1][g[1]]=v[1];
    for(i=2;i<=n;i++)
    {
        for(j=1;j<=G;j++)
        {
            dp[l2][j]=dp[l1][j];
            if(j>=g[i])dp[l2][j]=max(dp[l2][j],dp[l1][j-g[i]]+v[i]);
        }

        swap(l1,l2);
    }

    maxim=0;

    for(i=1;i<=G;i++)
        maxim=max(maxim,dp[l1][i]);

    fout<<maxim<<"\n";
    return 0;
}