#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,gg,i,j,g[5005],v[5005],sum[10005];
int main()
{
    fin>>n>>gg;
    for(int i=1;i<=n;i++)
        fin>>g[i]>>v[i];
    sum[0]=0;
    for(i=1;i<=n;i++)
        for(j=gg-g[i];j>=0;j--)
    {
        if(sum[j+g[i]]<sum[j]+v[i])
            sum[j+g[i]]=sum[j]+v[i];
    }
    fout<<sum[gg];
    return 0;
}