#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int v[5001], g[5001], dp[2][10001];
int main() {
    int n, G, x;
    fin >> n >> G;
    for (int i = 1; i <= n; i++)
        fin >> g[i] >> v[i];
    for (int i = 1; i <= n; i++)
        {
            for(int j=1; j<=G; j++)
            {
                x = dp[0][j];
                if(j >= g[i] && x <= dp[0][j - g[i]] + v[i])
                    x = dp[0][j - g[i]] + v[i];
                dp[1][j] = x;
            }
            for(int k = 1; k <= G; k++)
                dp[0][k] = dp[1][k];
        }
    int max = 0;
    for(int i=1; i<= G; i++)
        if(max < dp[1][i])
            max = dp[1][i];
    fout << max;
}