#include<fstream>
#include<cstring>
using namespace std;
ifstream cin ("rucsac.in");
ofstream cout("rucsac.out");

int g[5001],v[5001];
int dp [2][10001];

int main()
{
    int n,gm;cin>>n>>gm;
    for(int i=1;i<=n;i++)
        cin>>g[i]>>v[i];

    for (int i = 1; i <= n; i++)
    {
        for(int gr=1; gr<=gm; gr++)
        {
            dp[1][gr]=dp[0][gr];
            if (g[i]<=gr && v[i]+dp[0][gr-g[i]]>dp[1][gr])
                dp[1][gr] = v[i]+dp[0][gr-g[i]];
        }
        for (int gr=1; gr<=gm; gr++)
            dp[0][gr]=dp[1][gr];
    }
    cout << dp[0][gm];

    return 0;
}