#include <bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
void pd();
int v[10005],n,G,g[5005],c[5005],i,x;
int main()
{
    fin>>n>>G;
    for(i=1;i<=n;i++)
        fin>>g[i]>>c[i];
    pd();
    fout<<v[G];
    return 0;
}
void pd()
{
    for(i=1;i<=n;i++)
        for(x=G;x>0;x--)
        if(x>=g[i])
        if(v[x]<c[i]+v[x-g[i]])
        v[x]=c[i]+v[x-g[i]];
}