#include <fstream>
using namespace std;

ifstream is ("rucsac.in");
ofstream os ("rucsac.out");

int n, C, val[5001], w[5001];
int v[5001][10001];

void Read();

int main()
{
    Read();
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= C; ++j)
        {
            if (j >= w[i])
            {
                v[i][j] = val[i];
                v[i][j] += v[i-1][j-w[i]];
            }

            if (v[i][j] < v[i-1][j])
                v[i][j] = v[i-1][j];
            if (v[i][j] < v[i][j-1])
                v[i][j] = v[i][j-1];

        }
    }
    os << v[n][C];
    is.close();
    os.close();
    return 0;
}


void Read()
{
    is >> n;
    is >> C;
    for (int i = 1; i <= n; ++i)
    {
        is >> w[i] >> val[i];
    }
};