#include <bits/stdc++.h>
using namespace std;
ifstream in ("rucsac.in");
ofstream out ("rucsac.out");
int n,gr,i,j,mx,dp[5005][10005],x[5005],y[5005];
int main()
{
    ios_base::sync_with_stdio (false);
    cin.tie (0);
    cout.tie (0);
    in>>n>>gr;
    for(i=1;i<=n;++i)
        in>>y[i]>>x[i];
    for(i=1;i<=n;++i)
        for(j=1;j<=gr;++j)
    {
        dp[i][j]=dp[i-1][j];
        if(j>=y[i])
            dp[i][j]=max(dp[i][j],dp[i-1][j-y[i]]+x[i]);
        if(i==n)
            mx=max(mx,dp[i][j]);
    }
    out<<mx;
}