#include <cstdio>
#include <algorithm>

using namespace std;

/// https://www.infoarena.ro/problema/rucsac
int m[5001][10001]={0};
int n, g, i, j;

int weight[5001], profit[5001];

int main() {
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);

    scanf("%d%d", &n, &g);
    for (i=1; i<=n; i++)
        scanf("%d%d", &weight[i], &profit[i]);

    for (i=1; i<=n; i++)
    {
        for (j=0; j<=g; j++)
        {
            if (weight[i] <= j)
                m[i][j] = max(m[i-1][j], profit[i] + m[i-1][j-weight[i]]);
            else
                m[i][j] = m[i-1][j];
        }
    }

    printf("%d", m[n][g]);

    return 0;
}