#include <bits/stdc++.h>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int n, g, dp[2][10005];

struct
{
    int greutate, profit;
}a[5005];

void Citire()
{
    fin >> n >> g;
    for(int i = 1; i <= n; i++)
        fin >> a[i].greutate >> a[i].profit;
}

void Din()
{
    dp[0][a[1].greutate] = a[1].profit;

    int lin = 0;

    for(int i = 2; i <= n; i++)
    {
        lin = 1 - lin;

        for(int j = 1; j <= g; j++)
            if(j >= a[i].greutate)
                dp[lin][j] = max(dp[1 - lin][j], /// nu iau obiectul
                                 dp[1 - lin][j - a[i].greutate] + a[i].profit); /// il iau adaugand a[i].g la greutate
            else dp[lin][j] = dp[1 - lin][j];
    }

    int maxim = -1;

    for(int i = 1; i <= g; i++)
        maxim = max(maxim, dp[lin][i]);

    fout << maxim << " ";
}

int main()
{
    Citire();
    Din();
    return 0;
}