#include <bits/stdc++.h>
#define nmax 5005
#define gmax 10005

using namespace std;

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

int n,G,g[nmax],v[nmax],dp[nmax][gmax];

void Citire()
{
    fin >> n >> G;
    for(int i = 1; i <= n; i++)
        fin >> g[i] >> v[i];
}

void Dinamica()
{
    int i,j;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= G; j++)
            if(g[i] > j) dp[i][j] = dp[i-1][j];
            else dp[i][j] = max(dp[i-1][j],dp[i-1][j-g[i]] + v[i]);
}

void Afisare()
{
    fout << dp[n][G] << "\n";
}

int main()
{
    Citire();
    Dinamica();
    Afisare();
    fin.close();
    fout.close();
    return 0;
}