#include <iostream>
#include <fstream>
#define greutate first
#define profit second
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int dp[2][10005];
pair<int, int> obj[5005];
int main()
{
    int n, g;
    fin>>n>>g;
    for (int i=1; i<=n; i++) {
        fin>>obj[i].greutate>>obj[i].profit;
    }
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=g; j++) {
            int prof=obj[i].profit, greu=obj[i].greutate;
            if (greu>j) {
                dp[i%2][j]=dp[(i-1)%2][j];
            }
            else {
                dp[i%2][j]=max(dp[(i-1)%2][j], prof+dp[(i-1)%2][j-greu]);
            }
        }
    }
    fout<<dp[n%2][g];
    return 0;
}