#include <bits/stdc++.h>
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
void read();
struct obiect
{
    int g, v;
}a[5005];
int n, g;
int dp[2][10005];
int main()
{
    read();
    for(int i=1; i<=n; i++)
        for(int j=1; j<=g; j++)
        {
            dp[i%2][j] = dp[(i-1)%2][j];
            if(j-a[i].g >= 0)
                dp[i%2][j] = max(dp[i%2][j], dp[(i-1)%2][j-a[i].g]+a[i].v);
        }
    fout << dp[n%2][g];
    return 0;
}
void read()
{
    fin >> n >> g;
    for(int i=1; i<=n; i++)
        fin >> a[i].g >> a[i].v;
}