#include <fstream>
#define MAXN 5001
#define MAXG 10001

using namespace std;

struct
{
    int w;
    int p;
}rucsac[MAXN];
int dp[MAXG];

int main()
{
    int n, g, i, j, sol = 0;

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

    fin >> n >> g;

    for(i = 1; i <= n; i++)fin >> rucsac[i].w >> rucsac[i].p;

    for(i = 1; i <= n; i++)
        for(j = g - rucsac[i].w; j >= 0; j--)
            if(dp[j + rucsac[i].w] < dp[j] + rucsac[i].p)
            {
                dp[j + rucsac[i].w] = dp[j] + rucsac[i].p;
                if(sol < dp[j + rucsac[i].w])sol = dp[j + rucsac[i].w];
            }

    fout << sol;

    fin.close();
    fout.close();

    return 0;
}