#include <bits/stdc++.h>
using namespace std;

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

int N, G, D[10005], W[10005], P[5005];

int main()
{
    fin >> N >> G;
    for(int i=1; i<=N; ++i)fin >> W[i] >> P[i];
    for(int i = 1; i <= N; ++i)
    {
        for( int j = G; j >= W[i]; --j)
        {
            D[j] = max(D[j], D[j - W[i]] + P[i]);
        }
    }
    fout<<D[G];
    return 0;
}