#include <bits/stdc++.h>

using namespace std;

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

int n, g, mar, gre, mat[5001][10001];

int main()
{
    fin >> n >> g;

    for (int i = 1; i <= n; i ++)
    {
        fin >> mar >> gre;

        for (int j = 1; j <= g; j ++)
        {
            if (j >= mar)
                mat[i][j] = max(mat[i - 1][j - mar] + gre, mat[i - 1][j]);
            else
                mat[i][j] = mat[i - 1][j];
        }
    }

    fout << mat[n][g];

    return 0;
}