#include <bits/stdc++.h>

using namespace std;

int dp[2][10000];

//dp[i%2][j] -> profit maxim pt primele i obiecte, cu greutatea j

pair<int,int> v[5001];

int main()
{
    ifstream fin ("rucsac.in");
    ofstream fout ("rucsac.out");
    ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
    int n,g; fin>>n>>g;
    for(int i=1; i<=n; ++i) fin>>v[i].first>>v[i].second;
    int maxi=0;
    for(int i=1; i<=n; ++i)
    {
        dp[i%2][0] = 0;
        for(int j=1; j<=g; ++j)
        {
            dp[i%2][j] = 0;
            if(j >= v[i].first)
                dp[i%2][j] = max({dp[i%2][j], dp[(i-1)%2][j-v[i].first] + v[i].second, dp[(i-1)%2][j]});
            maxi = max(maxi, dp[i%2][j]);
        }
    }
    fout<<maxi;
//    for(int j=1; j<=g; ++j)
//    {
//        for(int i=1; i<=n; ++i)
//            cout<<dp[i][j]<<' ';
//        cout<<'\n';
//    }
    return 0;
}