#include <bits/stdc++.h>
using namespace std;

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

int n, w[5001], p[5001], dp[5001][50001], G, aux;
int main()
{
    fin>>n>>G;
    for(int i=1;i<=n;i++)
        fin>>w[i]>>p[i];
    for(int i=1;i<=n;i++)
        for(int g=1;g<=G;g++)
    {
        dp[i][g]=dp[i-1][g]; ///nu iau obiectul i
        if(g>=w[i]) ///incerc sa iau obiectul
            {
                aux=dp[i-1][g-w[i]]+p[i];
                if(aux>dp[i][g])
                    dp[i][g]=aux;
            }
    }
    fout<<dp[n][G];
}