#include<bits/stdc++.h>
 
using namespace std;
 
 
class Knapsack{
  public: 
    long long maximumValue(vector<int>& weights, vector<int>& values, int n, int capacity) {
      vector<vector<long long>> dp(n+1, vector<long long>(capacity+1, 0));
      for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= capacity; ++j) {
          if(weights[i-1] > j) dp[i][j] = dp[i-1][j];
          else {
            dp[i][j] = max(dp[i-1][j], values[i-1]+dp[i-1][j-weights[i-1]]);
          }
        }
      }
      return dp[n][capacity];
    }
};
 
 
int main() {
  int n, c; 
  cin >> n >> c;
  vector<int> weights(n), values(n);
 
  for(int i = 0; i < n; ++i) {
    cin >> weights[i] >> values[i];
  }
 
  Knapsack* obj = new Knapsack();
  cout << obj->maximumValue(weights, values, n, c);
  return 0;
}

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgoKY2xhc3MgS25hcHNhY2t7CiAgcHVibGljOiAKICAgIGxvbmcgbG9uZyBtYXhpbXVtVmFsdWUodmVjdG9yPGludD4mIHdlaWdodHMsIHZlY3RvcjxpbnQ+JiB2YWx1ZXMsIGludCBuLCBpbnQgY2FwYWNpdHkpIHsKICAgICAgdmVjdG9yPHZlY3Rvcjxsb25nIGxvbmc+PiBkcChuKzEsIHZlY3Rvcjxsb25nIGxvbmc+KGNhcGFjaXR5KzEsIDApKTsKICAgICAgZm9yKGludCBpID0gMTsgaSA8PSBuOyArK2kpIHsKICAgICAgICBmb3IoaW50IGogPSAxOyBqIDw9IGNhcGFjaXR5OyArK2opIHsKICAgICAgICAgIGlmKHdlaWdodHNbaS0xXSA+IGopIGRwW2ldW2pdID0gZHBbaS0xXVtqXTsKICAgICAgICAgIGVsc2UgewogICAgICAgICAgICBkcFtpXVtqXSA9IG1heChkcFtpLTFdW2pdLCB2YWx1ZXNbaS0xXStkcFtpLTFdW2otd2VpZ2h0c1tpLTFdXSk7CiAgICAgICAgICB9CiAgICAgICAgfQogICAgICB9CiAgICAgIHJldHVybiBkcFtuXVtjYXBhY2l0eV07CiAgICB9Cn07CgoKaW50IG1haW4oKSB7CiAgaW50IG4sIGM7IAogIGNpbiA+PiBuID4+IGM7CiAgdmVjdG9yPGludD4gd2VpZ2h0cyhuKSwgdmFsdWVzKG4pOwogIAogIGZvcihpbnQgaSA9IDA7IGkgPCBuOyArK2kpIHsKICAgIGNpbiA+PiB3ZWlnaHRzW2ldID4+IHZhbHVlc1tpXTsKICB9CiAgCiAgS25hcHNhY2sqIG9iaiA9IG5ldyBLbmFwc2FjaygpOwogIGNvdXQgPDwgb2JqLT5tYXhpbXVtVmFsdWUod2VpZ2h0cywgdmFsdWVzLCBuLCBjKTsKICByZXR1cm4gMDsKfQ==

MyA4CjMgMzAKNCA1MAo1IDYwCg==

3 8
3 30
4 50
5 60