using namespace std;

#include <set>
#include <map>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <utility>
#include <iomanip>
#include <fstream>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>

#define oo (1<<30)
#define f first
#define s second
#define II inline
#define db double
#define ll long long
#define pb push_back
#define mp make_pair
#define Size(V) ((ll)(V.size()))
#define all(V) (V).begin() , (V).end()
#define CC(V) memset((V),0,sizeof((V)))
#define CP(A,B) memcpy((A),(B),sizeof((B)))
#define FOR(i,a,b) for(ll (i)=(a);(i)<=(b);++(i))
#define REP(i, N) for (ll (i)=0;(i)<(ll)(N);++(i))
#define FORit(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); ++it)
#define printll(x) printf("%lld",(x))
#define printsp() printf(" ")
#define newline() printf("\n")
#define readll(x) scanf("%lld",&(x))
#define debugll(x) fprintf(stderr,"%lld\n",(x))

#define IN "rucsac.in"
#define OUT "rucsac.out"


int TAKEN = 43793;

int itemCount;
int maxWeight;

struct item
{
  int value;
  int weight;
};

int* bestValues;
map<int, int>** takens;

item* items;


void readItems()
{
  items = new item[itemCount];
  for (int i = 0; i < itemCount; i++)
  {
    cin >> items[i].weight;
    cin >> items[i].value;
  }
}

void initStructures()
{
  bestValues = new int[maxWeight + 1];
  

  takens = new map<int, int>*[maxWeight + 1];
  for (int i = 0; i <  maxWeight + 1; i++)
  {
//    takens[i] = new int[itemCount];
    takens[i] = new map<int, int>();
  } 

}


void putIn(int solIndex, int itemIndex);


void baseOnSolution(int newSol, int oldSol)
{

  map<int, int>::iterator it; 
  for (it = takens[oldSol]->begin(); it != takens[oldSol]->end(); it++)
  {
    putIn(newSol, (*it).first);
  } 
/*
  for (int i = 0; i < itemCount; i++)
  {
    takens[newSol][i] = takens[oldSol][i];
  }
*/
}

bool isIn(int solIndex, int itemIndex)
{
//  return takens[solIndex][itemIndex] == TAKEN;
  return takens[solIndex]->end() != takens[solIndex]->find(itemIndex);
}

void putIn(int solIndex, int itemIndex)
{
//  takens[solIndex][itemIndex] = TAKEN;
  takens[solIndex]->insert(pair<int, int> (itemIndex, TAKEN));
}


void solveKnapsack()
{
  initStructures();
  bestValues[0] = 0;
  for (int i = 1; i <= maxWeight; i++)
  {
    int maxVal = bestValues[i - 1];
    int objectIndex = -1;
//    cerr << i << endl; 
    for (int j = 0; j < itemCount; j++)
    {

      int prev = i - items[j].weight;
      if (items[j].weight <= i && !isIn(prev, j))
      {
        if (bestValues[prev] + items[j].value > maxVal)
        {
          maxVal = bestValues[prev] + items[j].value;
          objectIndex = j;
        }
      }
    } 

    bestValues[i] = maxVal;
    if (objectIndex != -1)
    {
      //cerr << objectIndex << endl;
      baseOnSolution(i, i - items[objectIndex].weight);
      putIn(i, objectIndex);
      //cout << i <<  " " << objectIndex << " taken" << << endl;
    }
    else
    {
       baseOnSolution(i, i - 1);
    } 
  }
}

void solve(int test) {
  cin >> itemCount;
  cin >> maxWeight; 
  readItems();
  solveKnapsack();

  cout << bestValues[maxWeight] << endl;

/*
  for (int i = 0; i < itemCount; i++)
  {
    if (takens[maxWeight][i] == TAKEN)
    {
      cerr << i << endl;
    }
  }
*/
}


int main() {
#ifndef ONLINE_JUDGE
  freopen(IN,"r",stdin);
  freopen(OUT,"w",stdout);
#endif
    solve(1);
  return 0;
}