#include <iostream>
#include <fstream>
using namespace std;

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

int N, G, greut, profit, i, j, s_max[10001], p_max;

int main()
{

    fin>>N>>G;

    for(i=1;i<=N;i++)
    {
        fin>>greut>>profit;

        for(j=G;j>=greut;j--)
        {
            s_max[j] = max(s_max[j], s_max[j-greut]+profit);
            p_max = max(p_max, s_max[j]);
        }

    }

    fout<< p_max;

    return 0;
}