#include <bits/stdc++.h>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int dp[2][10005];
int w[5002];
int p[5002];
int main()
{
    int n,i,G,l = 0,j;
    fin >> n >> G;
    for(i = 1; i <= n; i++){
        l ^= 1;
        fin >> w[i] >> p[i];
        for(j = 0; j < w[i]; j++) dp[l][j] = max(dp[l][j], dp[l ^ 1][j]);
        dp[l][w[i]] = max(dp[l][w[i]], p[i]);
        for(j = w[i] + 1; j <= G; j++){
            dp[l][j] = max(dp[l][j], dp[l ^ 1][j]);
            if(dp[l ^ 1][j - w[i]]) dp[l][j] = max(dp[l ^ 1][j], dp[l ^ 1][j - w[i]] + p[i]);
        }
    }
    int m = 0;
    for(i = 1; i <= G; i++) m = max(m, dp[l][i]);
    fout << m;
    return 0;
}