Icaro

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> ii;
typedef long long ll;

int n, s;
vector<ii> item;

vector<int> mul(vector<int> a, vector<int> b) {
  vector<int> ans(2001, -1e18);
  for(int i = 0; i < a.size(); ++i) {
    for(int j = 0; j < a.size(); ++j) {
      int id = (i + j) - 1000;
      if(0 <= id && id < a.size()){
        ans[id] = max(ans[id], a[i] + b[j]);
      }
    }
  }
  return ans;
}

int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0);
  vector<int> dp;
  cin >> n >> s;
  for(int i = 0; i < n; ++i) {
    int c, w;
    cin >> w >> c;
    item.push_back({c, w});
  }
  int m = 1000;
  dp.resize(2002, 0);
  for(int i = 0; i <= m; ++i) {
    for(int j = 0; j < n; ++j) {
      if(item[j].second <= i) {
        dp[i] = max(dp[i], dp[i - item[j].second] + item[j].first);
      }
    }
  }
  vector<int> ans(2001, -1e18);
  vector<int> aux(2001, -1e18);
  ans[m] = 0;
  for(int i = m; i < ans.size(); ++i) {
    aux[i - 1] = dp[i - m];
  }
  while(s) {
    if(s & 1) ans = mul(ans, aux);
    aux = mul(aux, aux);
    s >>= 1;
  }
  cout << ans[m] << '\n';
  return 0;
}