#include <bits/stdc++.h>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

const int nr=5001;

int n,gmax;
int valoare[nr],greutate[nr];
int r[nr][10001];

void citire()
{
    f>>n>>gmax;
    for(int i=1;i<=n;++i)
        f>>greutate[i]>>valoare[i];
}
void rezolvare()
{
    for(int i=1;i<=n;i++)
        for(int j=0;j<=gmax;j++)
        if(greutate[i]>j)r[i][j]=r[i-1][j];
        else r[i][j]=max(r[i-1][j],valoare[i]+r[i-1][j-greutate[i]]);

}

int main()
{
    ///r[i][j] este voloare maxima obtinuata din obiectele 1..i intr un rucsac
    ///cu capacitatea maxima j
    citire();
    rezolvare();
    g<<r[n][gmax];
}