#include <fstream>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int n, gm;
int dp[3][10001], g[5001], p[5001];

int main()
{
    fin >> n >> gm;
    for (int i = 1; i <= n; i++)
        fin >> g[i] >> p[i];
    int lin = 1;
    for (int i = 1; i <= n; i++){
        for(int j = 1; j <= gm; j++)
            if(j-g[i] >= 0)
            dp[lin][j]=max(dp[1-lin][j], dp[1-lin][j-g[i]]+p[i]);
            else
                dp[lin][j] = dp[1-lin][j];
        lin = 1-lin;
    }
    fout << dp[1-lin][gm];
    return 0;
}