#include <iostream>
#include <fstream>
#define NMAX 5005
struct ioniegaycuacte{
    long long cost,profit;
};
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int n,g;
ioniegaycuacte v[NMAX];
long long dp[10005];
int main()
{
    in>>n>>g;
    for(int i=1;i<=n;++i)
        in>>v[i].cost>>v[i].profit;
    for(int i=1;i<=n;++i){
        for(int j=g;j-v[i].cost>=0;--j)
            dp[j]=max(dp[j-v[i].cost]+v[i].profit,dp[j]);
    }
    out<<dp[g];
    return 0;
}