#include <stdio.h>
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i,a,b) for(int i = a; i < b; i++)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
// const int INF = 0x3f3f3f3f;
const int Gmax = 10444;
const int Nmax = 5333;

ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");

int N, G, W[Nmax], P[Nmax], dp[Gmax];

int main(void) {
  fin >> N >> G;
  rep(i, N) { fin >> W[i] >> P[i]; }

  rep(i, N) {
    for(int j = G - W[i]; j >= 0; --j) {
      dp[j+W[i]] = max(dp[j+W[i]], dp[j] + P[i]);
    }
  }
  fout << *max_element(dp, dp+G+1) << '\n';

  return 0;
}