#include <fstream>
#include <algorithm>

using namespace std;

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

int n,g, w[5004], p[5004];
long long dp[2][10004];


int main()
{
    cin>>n>>g;

for(int j=1; j<=n; ++j){
    cin>>w[j]>>p[j];
        for(int i=1; i<=g; ++i){
            dp[j%2][i] = max(dp[(j-1)%2][i],dp[j%2][i-1]);
            if(w[j]<=i) dp[j%2][i] = max(dp[j%2][i],dp[(j-1)%2][i-w[j]]+p[j]);

        }

}
    cout<<dp[n%2][g];


    return 0;
}