#include <bits/stdc++.h>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int a[1000][10000], n, g, m, val;
int main()
{
    fin >> n >> g;
    for(int i = 1; i <= n; ++ i)
    {
        fin >> m >> val;
        for(int j = 1; j <= g; ++ j)
            if(j >= m)
            a[1][j] = max(a[0][j], a[0][j - m] + val);
            else
            a[1][j] = a[0][j];
        for(int j = 1; j <= g; ++ j)
            a[0][j] = a[1][j];
    }
    fout << a[0][g];
    return 0;
}