#include <bits/stdc++.h>
using namespace std;

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

int greutate[1005],profit[1005];
int rucsac[1005][1005];

int main()
{
    int nr_obiecte,capacitate_max,i,j;

    f>>nr_obiecte>>capacitate_max;

    for (i=1;i<=nr_obiecte;i++)
        f>>greutate[i]>>profit[i];

    for (i=1;i<=nr_obiecte;i++) /// i = obiectul curent
    {
        for (j=1;j<=capacitate_max;j++) /// j = greutate curenta
        {
            rucsac[i][j] = rucsac[i-1][j];
            if (greutate[i]<=j)
                rucsac[i][j] = max(rucsac[i-1][j],rucsac[i-1][j-greutate[i]]+profit[i]);
        }
    }

    int raspuns=INT_MIN;
    for (i=1;i<=capacitate_max;i++)
        raspuns = max(rucsac[nr_obiecte][i],raspuns);

    g<<raspuns;

    return 0;
}