#include<cstdio>

using namespace std;

int v[10005];

int main()
{
  freopen("rucsac.in", "r", stdin);
  freopen("rucsac.out", "w", stdout);
  int n, i, j, x, y, max = 0, g;
  scanf("%d%d", &n, &g);
  for(i = 1; i <= n; ++ i)
  {
    scanf("%d%d", &x, &y);
    for(j = max; j > 0 ; -- j)
      if(j + x <= g && v[j])
        if(v[j + x] < v[j] + y)
          v[j + x] = v[j] + y;
    max = max + x;
    if(max > g)
      max = g;
    if(v[x] < y)
      v[x] = y;
  }
  max = 0;
  for(i = 1; i <= g; ++ i)
    if(v[i] > max)
      max = v[i];
  printf("%d", max);
  return 0;
}