#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int n,gmax,ma[5010][10010];
pair<int,int> v[5010];
int main()
{
    fin>>n>>gmax;
    for(int i=1;i<=n;i++)
        fin>>v[i].first>>v[i].second;

    for(int i=v[1].first;i<=gmax;i++)
        ma[1][i]=v[1].second;
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<v[i].first;j++)
            ma[i][j]=max(ma[i-1][j],ma[i][j-1]);
        for(int j=v[i].first;j<=gmax;j++)
            ma[i][j]=max(ma[i-1][j-v[i].first]+v[i].second,max(ma[i-1][j],ma[i][j-1]));
    }

    fout<<ma[n][gmax];
    return 0;
}