#include <bits/stdc++.h>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int const gmax=10007, lmax=5007;
int dp[2][gmax];
int n,gtotal;
int profit[lmax];
int kg[lmax];
int main()
{
    fin>>n>>gtotal;
    for(int i=1;i<=n;i++)
    {
        fin>>kg[i]>>profit[i];
    }
    int altern=0;
    for(int i=1;i<=n;i++)
    {
        altern=1-altern;
        for(int j=1;j<=gtotal;j++)
        {
            if(j-kg[i]<0)continue;
            dp[altern][j]=max(dp[1-altern][j],dp[1-altern][j-kg[i]]+profit[i]);
        }
    }
    fout<<dp[altern][gtotal];
    fin.close();
    fout.close();
    return 0;
}