#include <fstream>
#include <iostream>

using namespace std;

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

int n, dp[2][10006], m, ans;

/**
    RECURENTA
    dp[i][j] = profitul maxim de pe primele i obicte care au greutatea j
*/

struct DB
{
    int greutate, profit;
};
DB a[5006];
void Citire()
{
    int i;

    fin >> n >> m;

    for(i = 1; i <= n; i++)
        fin >> a[i].greutate >> a[i].profit;
}

void Dinamica()
{
    int i, j, lin = 0;

    ///initializare

    dp[0][a[1].greutate] = a[1].profit;

    ///dinamica
    for(i = 2; i <= n; i++)
    {
        lin = 1 - lin;
        for(j = 1; j <= m; j++)
            if(j >= a[i].greutate)
                dp[lin][j] = max(dp[1 - lin][j], dp[1 - lin][j - a[i].greutate] + a[i].profit);
            else
                dp[lin][j] = dp[1 - lin][j];
    }

    for(i = 1; i <= m; i++)
        ans = max(ans, dp[lin][i]);
    fout << ans << "\n";
}
int main()
{
    Citire();
    Dinamica();
    return 0;
}