#include <bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int dp[2][10005];
int w[5005], p[5005];
int main()
{
    int n, g, lin=1;
    fin >> n >> g;
    for(int i=1; i <= n; i++)
        fin >> w[i] >> p[i];
    dp[0][w[1]]=p[1];
    /// dp[i][j] = profitul maxim pe care pot sa-l obtin din primele i elemente avand greutatea totala j
    for(int i=2; i <= n; i++)
    {
        for(int j=0; j <= g; j++)
        {
            dp[lin][j]=dp[1-lin][j];
            if(j >= w[i])
                dp[lin][j]=max(dp[lin][j], dp[1-lin][j-w[i]]+p[i]);
        }
        lin=1-lin;
    }
    int rez=0;
    for(int i=0; i <= g; i++)
        rez=max(dp[1-lin][i], rez);
    fout << rez;
    return 0;
}