#include <iostream>
#include <fstream>
using namespace std;
int d[10010];
int g[5010],p[5010];
int maxim,i,j;
int n,q;
int main()
{
    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");
  fin>>n>>q;
  for( i=1;i<=n;i++)
    fin>>g[i]>>p[i];

d[0]=1;
    for(i=1;i<=n;i++)
        for(j=q;j>=0;j--)
    {
        if(d[j] !=0 && j+g[i]<=q)
        {
            d[j+g[i]]=max(d[j+g[i]],d[j]+p[i]);
        }
    }
    for (i=0;i<=q;i++)
        maxim=max(maxim,d[i]);
    fout<<maxim-1;
}