#include<bits/stdc++.h>
 
using namespace std;
 
 
class Knapsack{
  public: 
    long long maximumValue(vector<int>& weights, vector<int>& values, int n, int capacity) {
      vector<long long> dp(capacity+1, 0);
      for(int i = 1; i <= n; ++i) {
        for(int j = capacity; j >= weights[i-1]; --j) {
            dp[j] = max(dp[j-1], values[i-1]+dp[j-weights[i-1]]);
        }
      }
      return dp[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+JiB2YWx1ZXMsIGludCBuLCBpbnQgY2FwYWNpdHkpIHsKICAgICAgdmVjdG9yPGxvbmcgbG9uZz4gZHAoY2FwYWNpdHkrMSwgMCk7CiAgICAgIGZvcihpbnQgaSA9IDE7IGkgPD0gbjsgKytpKSB7CiAgICAgICAgZm9yKGludCBqID0gY2FwYWNpdHk7IGogPj0gd2VpZ2h0c1tpLTFdOyAtLWopIHsKICAgICAgICAgICAgZHBbal0gPSBtYXgoZHBbai0xXSwgdmFsdWVzW2ktMV0rZHBbai13ZWlnaHRzW2ktMV1dKTsKICAgICAgICB9CiAgICAgIH0KICAgICAgcmV0dXJuIGRwW2NhcGFjaXR5XTsKICAgIH0KfTsKCgppbnQgbWFpbigpIHsKICBpbnQgbiwgYzsgCiAgY2luID4+IG4gPj4gYzsKICB2ZWN0b3I8aW50PiB3ZWlnaHRzKG4pLCB2YWx1ZXMobik7CiAgCiAgZm9yKGludCBpID0gMDsgaSA8IG47ICsraSkgewogICAgY2luID4+IHdlaWdodHNbaV0gPj4gdmFsdWVzW2ldOwogIH0KICAKICBLbmFwc2Fjayogb2JqID0gbmV3IEtuYXBzYWNrKCk7CiAgY291dCA8PCBvYmotPm1heGltdW1WYWx1ZSh3ZWlnaHRzLCB2YWx1ZXMsIG4sIGMpOwogIHJldHVybiAwOwp9

MyA4CjMgMzAKNCA1MAo1IDYwCg==

3 8
3 30
4 50
5 60