#include <cstdio>
#include <algorithm>

using namespace std;

const int NMAX = 5005, GMAX = 10005;
struct obiect{
    int value, weight;
} v[NMAX];
int dp[GMAX], aux[GMAX];
int main()
{
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    int n, g, i, j;
    scanf("%d%d", &n, &g);
    for(i = 1; i <= n; ++i)
        scanf("%d%d", &v[i].weight, &v[i].value);
    for(i = 1; i <= n; ++i){
        for(j = 1; j <= g; ++j){
            if(v[i].weight <= j)
            {
                aux[j]=dp[j];
                dp[j] = max(dp[j], aux[j-v[i].weight]+v[i].value);
            }
        }
    }
    printf("%d", dp[g]);
    return 0;
}