#include <fstream>
using namespace std;

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

int dp[5001][10001];

int main()
{
    int n,m,i,j,rasp=0,a,b;
    cin>>n>>m;
    for(i=0;i<=n;i++){
        for(j=1;j<=m;j++){
            dp[i][j]=-1;
        }
    }
    for(i=1;i<=n;i++){
        cin>>a>>b;
        for(j=1;j<=m;j++){
            dp[i][j]=dp[i-1][j];
            if(j>=a && dp[i-1][j-a]!=-1) dp[i][j]=max(dp[i][j],dp[i-1][j-a]+b);
        }
    }
    for(i=0;i<=m;i++) rasp=max(rasp,dp[n][i]);
    cout<<rasp;
    return 0;
}