#include <iostream>
#include <fstream>
#define NUM 5005
int mat[NUM][2*NUM];
int gr[NUM];
int val[NUM];
int n, G;
using namespace std;
int maxim(int a, int b)
{
    return (a > b) ? a : b;
}
int profit()
{
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= G; ++j)
        {
            mat[i][j] = mat[i - 1][j];

            if(gr[i - 1] <= j)
                mat[i][j] = maxim(mat[i - 1][j - gr[i - 1]] + val[i - 1], mat[i - 1][j]);
        }
    }
    return mat[n][G];
}
int main()
{
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
    f >> n >> G;
    for(int i = 0; i < n; ++i)
        f >> gr[i] >> val[i];
    g << profit();
    f.close();
    g.close();
}