#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;


#define nmax 5001
#define gmax 10001

int P[nmax], W[nmax], Best[gmax], N, G;


int main()
{
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    int i, j, sol = 0;
    scanf("%i %i", &N, &G);
    for(i = 1; i <= N; i++)
          scanf("%i %i", &W[i], &P[i]);
    Best[0] = 0;
    for(i = 1; i <= N; i++)
    {
          for(j = G - W[i]; j >= 0; j--)
          {
                if(Best[j + W[i]] < Best[j] + P[i])
                {
                          Best[j + W[i]] = max(Best[j + W[i]], Best[j] + P[i]);
                          sol = max(sol, Best[j + W[i]]);
                }
          }
    }
    printf("%i\n", sol);
    scanf("%i", &i);
    return 0;
}