#include <bits/stdc++.h>

using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int n,G,w[5005],p[5005],d[5005][10005],i,g;
int main()
{
    fin>>n>>G;
    for (i=1;i<=n;i++)
        fin>>w[i]>>p[i];
    for (i=1;i<=n;i++)
        {
            for (g=0;g<=G;g++)
                {
                    d[i][g]=d[i-1][g];
                    if (w[i]<=g)
                        d[i][g]=max(d[i-1][g],p[i]+d[i-1][g-w[i]]);
                }
        }
    fout<<d[n][G];
    return 0;
}