#include <bits/stdc++.h>

using namespace std;

ifstream in("rucsac.in");
ofstream out("rucsac.out");
int N,G,W[5001],P[5001],m[2][10001];

int main()
{
    in>>N>>G;
    for(int i=1;i<=N;i++)
        in>>W[i]>>P[i];
    bool ok=0;
    for(int i=0;i<N;i++;ok=1-ok)
    {
        for(int j=0;j<=G;j++)
            m[1-ok][j]=m[ok][j];
        if(W[i]<=j)
            m[1-ok][j]=max(m[1-ok][j],m[ok][j-W[i]]+P[i]);
    }
    return 0;
}