#include <bits/stdc++.h>

using namespace std;

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

const int Nmax = 5005;
const int Gmax = 10005;

int n, G;
int dp[Nmax][Gmax], c[Nmax], v[Nmax];

void Read()
{
    int i;
    fin >> n >> G;
    for(i = 1; i <= n; i++)
        fin >> c[i] >> v[i];
    fin.close();
}

void DP()
{
    int i, j, maxi, lin;
    lin = 0;
    dp[lin][c[1]] = v[1];
    for(i = 2 ; i <= n ; i++)
    {
        lin = 1 - lin;
        for(j = 1 ; j <= G ; j++)
        {
            dp[lin][j] = dp[1 - lin][j];
            if(j >= c[i])
                dp[lin][j] = max(dp[lin][j] , dp[1 - lin][j - c[i]] + v[i]);
        }
    }
    maxi = -1;
    for(i = 1 ; i <= G ; i++)
        maxi = max(maxi , dp[lin][i]);
    fout << maxi << "\n";
    fout.close();
}

int main()
{
    Read();
    DP();
    return 0;
}