import std.stdio;
import std.conv;
import std.string;
import std.format;
import std.algorithm;

//string lines = q"[
//abcdeffg]";

void main()
{
  string lines;
  string buf;

  while (!stdin.eof) {
    buf = stdin.readln();
    lines ~= buf;
  }

  string[] array = splitLines(lines);
    
  int N = array[0].split(" ")[0].to!int;
  int W = array[0].split(" ")[1].to!int;
    
  long[] Wi = new long[](N+1);
  long[] Vi = new long[](N+1);
  Wi[0] = 0L;
  Vi[0] = 0L;

  for (int i=1; i<array.length; i++) {
    string s = array[i];
    Wi[i] = s.split(" ")[0].to!int;
    Vi[i] = s.split(" ")[1].to!int;
  }
  
  long[][] dp = new long[][](N+1,W+1);
  for (int i = 1; i < N+1; i++) {
    for (int j = 1; j < W+1; j++) {
      if (j < Wi[i]) {
        dp[i][j] = dp[i-1][j];
      } else {
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-Wi[i]] + Vi[i]);
      }
    }
  }
  writeln(dp.reduce!(max).reduce!(max));
}