#include <iostream>
#include <fstream>

using namespace std;

ifstream f("rucsac.in");
ofstream o("rucsac.out");
struct obiect
{
    int greutate,profit;
};

int main()
{
    int n,g; f>>n>>g;
    int dp[n+1][g+1];

    for(int j=0;j<=g;j++) dp[0][j]=0;

    obiect rucsac[n+1];

    for(int i=1;i<=n;i++)
        f>>rucsac[i].greutate>>rucsac[i].profit;

    for(int i=1;i<=n;i++)
        for(int j=0;j<=g;j++)
        {
            if(rucsac[i].greutate>j) dp[i][j]=dp[i-1][j];
            else
                dp[i][j]=max(rucsac[i].profit+dp[i-1][j-rucsac[i].greutate],dp[i-1][j]);
        }

    o<<dp[n][g];

    return 0;
}