#include <iostream>
#include <fstream>
#define NR 10000

using namespace std;

ifstream f("rucsac.in");
ofstream wr("rucsac.out");

int n,g,vCitire[NR][2],dp[NR][NR];

void fillDp()
{
     for(int i=1;i<=n;i++)
        for(int j=vCitire[i][1];j<=g;j++)
        dp[i][j]=max(dp[i-1][j],dp[i-1][j-vCitire[i][1]]+vCitire[i][2]);
}

void citire()
{
    for(int i=1;i<=n;i++)
        f>>vCitire[i][1]>>vCitire[i][2];
}

int main()
{
    f>>n>>g;
    citire();
    fillDp();
    wr<<dp[n][g];


    return 0;
}