#include <fstream>
#include <algorithm>
using namespace std;
ifstream input("rucsac.in");
ofstream print("rucsac.out");
long dp[10002];
int greutate[5002],castig[5002];
int g,n,i,j;

int main(){
    input>>n>>g;
    for(i=1;i<=n;i++)
        input>>greutate[i]>>castig[i];
    for(i=1;i<=n;i++)
       for(j=g;j>=greutate[i];j--)
           dp[j]=max(dp[j],dp[j-greutate[i]]+castig[i]);
    print<<dp[g];
    return 0;
}