#include <bits/stdc++.h>
#define MAXN 5010
#define MAXG 10010
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

//solutia cu matrice
int main()
{
    int n, g;
    int w[MAXN], p[MAXN];
    int D[MAXN][MAXG];
    fin>>n>>g;
    for(int i=1; i<=n; i++)
        fin>>w[i]>>p[i];

    for(int i=1; i<=n; i++)
        for(int cw = 0; cw <= g; cw++)
        {
            D[i][cw] = D[i-1][cw];

            if(w[i] <= cw)
                D[i][cw] = max(D[i][cw], D[i - 1][cw - w[i]] + p[i]);
        }


    fout<<D[n][g];
}