#include <iostream>
#include <fstream>

using namespace std;

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

int dp[10005];
int nr_obiecte, greutate_maxima;

struct s{
    int g, val;
}obiecte[5005];

void dinamica()
{
    for (int i=1; i<=nr_obiecte; i++)
    {
        for (int j=greutate_maxima; j>=1; j--)
        {
            if (j-obiecte[i].g<0)
                continue;
            dp[j]=max(dp[j],dp[j-obiecte[i].g]+obiecte[i].val);
        }
    }
    int maxi=0;
    for (int j=1; j<=greutate_maxima; j++)
    {
        if (dp[j]>maxi)
            maxi=dp[j];
    }
    g << maxi;
}

int main()
{
    f >> nr_obiecte >> greutate_maxima;
    for (int i=1; i<=nr_obiecte; i++)
    {
        f >> obiecte[i].g >> obiecte[i].val;

    }
    dinamica();
    return 0;
}