#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;
    dp[1][c[1]] = v[1];
    for(i = 2; i <= n; i++)
        for(j = 1; j <= G; j++)
        if(j - c[i] >= 0) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + v[i]);
    else dp[i][j] = dp[i - 1][j];

    maxi = -1;

    for(i = 1; i <= G; i++)
        maxi = max(dp[n][i], maxi);
    fout << maxi;
    fout.close();
}

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