#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
struct obiecte{double value;int w;int p;}v[5003];
int i,n,gr,weight,profit,s=0,umm[10003];
bool srt(obiecte x,obiecte y)
{
    if(x.value>y.value)return 0;
    else if(x.value==y.value && x.w<y.w)return 0;
    return 1;
}
int main()
{
    f>>n>>gr;
    for(i=1;i<=n;i++)
    {
        f>>weight>>profit;
        v[i].w=weight;
        v[i].p=profit;
        //v[i].value=(double)((double)(profit)/weight);
    }
    //sort(v+1,v+n+1,srt);
    i=n;
    for(i=1;i<=n;i++)
        for(int j=gr;j>=v[i].w;j--)
        {
            umm[j]=max(umm[j],umm[j-v[i].w]+v[i].p);
        }
    g<<umm[gr];
}