stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
/*

Educational DP Contest - D - Knapsack 1

https://atcoder.jp/contests/dp/tasks/dp_d

*/



#include <bits/stdc++.h>

using namespace std; 

#define FAST_INP  ios_base::sync_with_stdio(false);cin.tie(NULL)

typedef long long ll; 

 

int main()  

{ 

    FAST_INP;

    ll n,W,w,v;

    cin >> n >> W;

    ll dp[100005];

    memset(dp,0,sizeof(dp));

    for(int i=0;i<n;i++){

    	cin >> w >> v;

    	for(int j=W;j>=w;j--){

    		dp[j]=max(dp[j],dp[j-w]+v);

		}	

	}

	cout << dp[W] << endl;

    return 0;

} 


// Faster C++ solution for the same problem (measured speedup: 1.795004811711615x):
/*

Educational DP Contest - D - Knapsack 1

https://atcoder.jp/contests/dp/tasks/dp_d

*/



#include <bits/stdc++.h>

using namespace std; 

#define FAST_INP  ios_base::sync_with_stdio(false);cin.tie(NULL)

typedef long long ll; 

 

int main()  

{ 

    FAST_INP;

    ll n,W,w,v;

    cin >> n >> W;

    ll dp[W+1];

    memset(dp,0,sizeof(dp));

    for(int i=0;i<n;i++){

    	cin >> w >> v;

    	for(int j=W;j>=w;j--){

    		dp[j]=max(dp[j],dp[j-w]+v);

		}	

	}

	cout << dp[W] << endl;

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef vector<ll> vll;

typedef vector<string> vs;

ll llmax = LLONG_MAX;

string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

string alp = "abcdefghijklmnopqrstuvwxyz";

vi d1 = {1, 0, -1, 0}, d2 = {0, 1, 0, -1};

void Yes() {cout << "Yes" << endl;}

void No() {cout << "No" << endl;}

void YES() {cout << "YES" << endl;}

void NO() {cout << "NO" << endl;}

void neg() {cout << -1 << endl;}



int main() {

  ll n, ww;

  cin >> n >> ww;

  vll w(n), v(n);

  for (ll i = 0; i < n; i++) cin >> w[i] >> v[i];

  vll dp(100001, 0);

  vector<vll> check(100001, vll(0));

  vll x(n, 0);

  check[0] = x;

  for (ll i = 1; i <= ww; i++) {

    dp[i] = dp[i - 1];

    ll memo = -1;

    for (ll j = 0; j < n; j++) {

      if (i < w[j]) continue;

      if (check[i - w[j]][j] == 1) continue;

      if (dp[i] < dp[i - w[j]] + v[j]) {

        dp[i] = dp[i - w[j]] + v[j];

        memo = j;

      }

    }

    if (memo != -1) {

      check[i] = check[i - w[memo]];

      check[i][memo] = 1;

    }

    else check[i] = check[i - 1];

  }

  cout << dp[ww] << endl;

}

// Faster C++ solution for the same problem (measured speedup: 2.4604463075047325x):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef vector<ll> vll;

typedef vector<string> vs;

ll llmax = LLONG_MAX;

string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

string alp = "abcdefghijklmnopqrstuvwxyz";

vi d1 = {1, 0, -1, 0}, d2 = {0, 1, 0, -1};

void Yes() {cout << "Yes" << endl;}

void No() {cout << "No" << endl;}

void YES() {cout << "YES" << endl;}

void NO() {cout << "NO" << endl;}

void neg() {cout << -1 << endl;}



int main() {

  ll n, lim;

  cin >> n >> lim;

  vll w(n), v(n);

  for (ll i = 0; i < n; i++) cin >> w[i] >> v[i];

  vll dp(100001, 0);

  vector<vll> check(1, vll(n, 0));

  for (ll i = 1; i <= lim; i++) {

    dp[i] = dp[i - 1];

    ll memo = -1;

    for (ll j = 0; j < n; j++) {

      if (i < w[j]) continue;

      if (check[i - w[j]][j] == 1) continue;

      if (dp[i] < dp[i - w[j]] + v[j]) {

        dp[i] = dp[i - w[j]] + v[j];

        memo = j;

      }

    }

    if (memo != -1) {

      vll x = check[i - w[memo]];

      x[memo] = 1;

      check.push_back(x);

    }

    else check.push_back(check[i - 1]);

  }

  cout << dp[lim] << endl;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef vector<ll> vll;

typedef vector<string> vs;

ll llmax = LLONG_MAX;

string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

string alp = "abcdefghijklmnopqrstuvwxyz";

vi d1 = {1, 0, -1, 0}, d2 = {0, 1, 0, -1};

void Yes() {cout << "Yes" << endl;}

void No() {cout << "No" << endl;}

void YES() {cout << "YES" << endl;}

void NO() {cout << "NO" << endl;}

void neg() {cout << -1 << endl;}



int main() {

  ll n, ww;

  cin >> n >> ww;

  vll w(n), v(n);

  for (ll i = 0; i < n; i++) cin >> w[i] >> v[i];

  vll dp(100001, 0);

  vector<vll> check(1, vll(n, 0));

  for (ll i = 1; i <= ww; i++) {

    dp[i] = dp[i - 1];

    ll memo = -1;

    for (ll j = 0; j < n; j++) {

      if (i < w[j]) continue;

      if (check[i - w[j]][j] == 1) continue;

      if (dp[i] < dp[i - w[j]] + v[j]) {

        dp[i] = dp[i - w[j]] + v[j];

        memo = j;

      }

    }

    if (memo != -1) {

      vll x = check[i - w[memo]];

      x[memo] = 1;

      check.push_back(x);

    }

    else check.push_back(check[i - 1]);

  }

  cout << dp[ww] << endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.8080226096239866x):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<ll> vll;

#define all(x) (x).begin(), (x).end()

#define endl '\n'

const ll inf = LLONG_MAX;

long double pi = M_PI;

void Yes() {cout << "Yes" << endl;}

void No() {cout << "No" << endl;}

void YES() {cout << "YES" << endl;}

void NO() {cout << "NO" << endl;}



int main() {

  ll n, w;

  cin >> n >> w;

  vll ww(n), v(n);

  for (ll i = 0; i < n; i++) cin >> ww[i] >> v[i];



  vll dp(w + 1, 0);

  vector<vll> check(1, vll(n, 0));

  for (ll i = 1; i <= w; i++) {

    dp[i] = dp[i - 1];

    ll memo = -1;

    for (ll j = 0; j < n; j++) {

      if (ww[j] <= i && check[max(0ll, i - ww[j])][j] == 0 && dp[i] < dp[max(0ll, i - ww[j])] + v[j]) {

        dp[i] = dp[max(0ll, i - ww[j])] + v[j];

        memo = j;

      }

    }

    if (memo == -1) check.push_back(check.back());

    else {

      check.push_back(check[max(0ll, i - ww[memo])]);

      check.back()[memo] = 1;

    }

  }

  cout << dp[w] << endl;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef vector<ll> vll;

typedef vector<string> vs;

ll llmax = LLONG_MAX;

string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

string alp = "abcdefghijklmnopqrstuvwxyz";

vi d1 = {1, 0, -1, 0}, d2 = {0, 1, 0, -1};

void Yes() {cout << "Yes" << endl;}

void No() {cout << "No" << endl;}

void YES() {cout << "YES" << endl;}

void NO() {cout << "NO" << endl;}

void neg() {cout << -1 << endl;}



int main() {

  ll n, ww;

  cin >> n >> ww;

  vll w(n), v(n);

  for (ll i = 0; i < n; i++) cin >> w[i] >> v[i];

  vll dp(100001, 0);

  vector<vll> check(1, vll(n, 0));

  for (ll i = 1; i <= ww; i++) {

    dp[i] = dp[i - 1];

    ll memo = -1;

    for (ll j = 0; j < n; j++) {

      if (i < w[j]) continue;

      if (check[i - w[j]][j] == 1) continue;

      if (dp[i] < dp[i - w[j]] + v[j]) {

        dp[i] = dp[i - w[j]] + v[j];

        memo = j;

      }

    }

    if (memo != -1) {

      check.emplace_back(check[i - w[memo]]);

      check[i][memo] = 1;

    }

    else check.emplace_back(check[i - 1]);

  }

  cout << dp[ww] << endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.807442196631453x):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<ll> vll;

#define all(x) (x).begin(), (x).end()

#define endl '\n'

const ll inf = LLONG_MAX;

long double pi = M_PI;

void Yes() {cout << "Yes" << endl;}

void No() {cout << "No" << endl;}

void YES() {cout << "YES" << endl;}

void NO() {cout << "NO" << endl;}



int main() {

  ll n, w;

  cin >> n >> w;

  vll ww(n), v(n);

  for (ll i = 0; i < n; i++) cin >> ww[i] >> v[i];



  vll dp(w + 1, 0);

  vector<vll> check(1, vll(n, 0));

  for (ll i = 1; i <= w; i++) {

    dp[i] = dp[i - 1];

    ll memo = -1;

    for (ll j = 0; j < n; j++) {

      if (ww[j] <= i && check[max(0ll, i - ww[j])][j] == 0 && dp[i] < dp[max(0ll, i - ww[j])] + v[j]) {

        dp[i] = dp[max(0ll, i - ww[j])] + v[j];

        memo = j;

      }

    }

    if (memo == -1) check.push_back(check.back());

    else {

      check.push_back(check[max(0ll, i - ww[memo])]);

      check.back()[memo] = 1;

    }

  }

  cout << dp[w] << endl;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef vector<ll> vll;

typedef vector<string> vs;

ll llmax = LLONG_MAX;

string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

string alp = "abcdefghijklmnopqrstuvwxyz";

vi d1 = {1, 0, -1, 0}, d2 = {0, 1, 0, -1};

void Yes() {cout << "Yes" << endl;}

void No() {cout << "No" << endl;}

void YES() {cout << "YES" << endl;}

void NO() {cout << "NO" << endl;}

void neg() {cout << -1 << endl;}



int main() {

  ll n, ww;

  cin >> n >> ww;

  vll w(n), v(n);

  for (ll i = 0; i < n; i++) cin >> w[i] >> v[i];

  vll dp(100001, 0);

  vector<vll> check(100001, vll(0));

  vll x(n, 0);

  check[0] = x;

  for (ll i = 1; i <= ww; i++) {

    dp[i] = dp[i - 1];

    ll memo = -1;

    for (ll j = 0; j < n; j++) {

      if (i < w[j]) continue;

      if (check[i - w[j]][j] == 1) continue;

      if (dp[i] < dp[i - w[j]] + v[j]) {

        dp[i] = dp[i - w[j]] + v[j];

        memo = j;

      }

    }

    if (memo != -1) {

      check[i] = check[i - w[memo]];

      check[i][memo] = 1;

    }

    else check[i] = check[i - 1];

  }

  cout << dp[ww] << endl;

}

// Faster C++ solution for the same problem (measured speedup: 4.448542553734408x):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<ll> vll;

#define all(x) (x).begin(), (x).end()

#define endl '\n'

const ll inf = LLONG_MAX;

long double pi = M_PI;

void Yes() {cout << "Yes" << endl;}

void No() {cout << "No" << endl;}

void YES() {cout << "YES" << endl;}

void NO() {cout << "NO" << endl;}



int main() {

  ll n, w;

  cin >> n >> w;

  vll ww(n), v(n);

  for (ll i = 0; i < n; i++) cin >> ww[i] >> v[i];



  vll dp(w + 1, 0);

  vector<vll> check(1, vll(n, 0));

  for (ll i = 1; i <= w; i++) {

    dp[i] = dp[i - 1];

    ll memo = -1;

    for (ll j = 0; j < n; j++) {

      if (ww[j] <= i && check[max(0ll, i - ww[j])][j] == 0 && dp[i] < dp[max(0ll, i - ww[j])] + v[j]) {

        dp[i] = dp[max(0ll, i - ww[j])] + v[j];

        memo = j;

      }

    }

    if (memo == -1) check.push_back(check.back());

    else {

      check.push_back(check[max(0ll, i - ww[memo])]);

      check.back()[memo] = 1;

    }

  }

  cout << dp[w] << endl;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef vector<ll> vll;

typedef vector<string> vs;

ll llmax = LLONG_MAX;

string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

string alp = "abcdefghijklmnopqrstuvwxyz";

vi d1 = {1, 0, -1, 0}, d2 = {0, 1, 0, -1};

void Yes() {cout << "Yes" << endl;}

void No() {cout << "No" << endl;}

void YES() {cout << "YES" << endl;}

void NO() {cout << "NO" << endl;}

void neg() {cout << -1 << endl;}



int main() {

  ll n, lim;

  cin >> n >> lim;

  vll w(n), v(n);

  for (ll i = 0; i < n; i++) cin >> w[i] >> v[i];

  vll dp(100001, 0);

  vector<vll> check(1, vll(n, 0));

  for (ll i = 1; i <= lim; i++) {

    dp[i] = dp[i - 1];

    ll memo = -1;

    for (ll j = 0; j < n; j++) {

      if (i < w[j]) continue;

      if (check[i - w[j]][j] == 1) continue;

      if (dp[i] < dp[i - w[j]] + v[j]) {

        dp[i] = dp[i - w[j]] + v[j];

        memo = j;

      }

    }

    if (memo != -1) {

      vll x = check[i - w[memo]];

      x[memo] = 1;

      check.push_back(x);

    }

    else check.push_back(check[i - 1]);

  }

  cout << dp[lim] << endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.8080226096239866x):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<ll> vll;

#define all(x) (x).begin(), (x).end()

#define endl '\n'

const ll inf = LLONG_MAX;

long double pi = M_PI;

void Yes() {cout << "Yes" << endl;}

void No() {cout << "No" << endl;}

void YES() {cout << "YES" << endl;}

void NO() {cout << "NO" << endl;}



int main() {

  ll n, w;

  cin >> n >> w;

  vll ww(n), v(n);

  for (ll i = 0; i < n; i++) cin >> ww[i] >> v[i];



  vll dp(w + 1, 0);

  vector<vll> check(1, vll(n, 0));

  for (ll i = 1; i <= w; i++) {

    dp[i] = dp[i - 1];

    ll memo = -1;

    for (ll j = 0; j < n; j++) {

      if (ww[j] <= i && check[max(0ll, i - ww[j])][j] == 0 && dp[i] < dp[max(0ll, i - ww[j])] + v[j]) {

        dp[i] = dp[max(0ll, i - ww[j])] + v[j];

        memo = j;

      }

    }

    if (memo == -1) check.push_back(check.back());

    else {

      check.push_back(check[max(0ll, i - ww[memo])]);

      check.back()[memo] = 1;

    }

  }

  cout << dp[w] << endl;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef vector<ll> vll;

typedef vector<string> vs;

ll llmax = LLONG_MAX;

string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

string alp = "abcdefghijklmnopqrstuvwxyz";

vi d1 = {1, 0, -1, 0}, d2 = {0, 1, 0, -1};

void Yes() {cout << "Yes" << endl;}

void No() {cout << "No" << endl;}

void YES() {cout << "YES" << endl;}

void NO() {cout << "NO" << endl;}

void neg() {cout << -1 << endl;}



int main() {

  ll n, ww;

  cin >> n >> ww;

  vll w(n), v(n);

  for (ll i = 0; i < n; i++) cin >> w[i] >> v[i];

  vll dp(100001, 0);

  vector<vll> check(1, vll(n, 0));

  for (ll i = 1; i <= ww; i++) {

    dp[i] = dp[i - 1];

    ll memo = -1;

    for (ll j = 0; j < n; j++) {

      if (i < w[j]) continue;

      if (check[i - w[j]][j] == 1) continue;

      if (dp[i] < dp[i - w[j]] + v[j]) {

        dp[i] = dp[i - w[j]] + v[j];

        memo = j;

      }

    }

    if (memo != -1) {

      vll x = check[i - w[memo]];

      x[memo] = 1;

      check.push_back(x);

    }

    else check.push_back(check[i - 1]);

  }

  cout << dp[ww] << endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.8124083818714114x):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<ll> vll;

#define all(x) (x).begin(), (x).end()

#define endl '\n'

const ll inf = LLONG_MAX;

long double pi = M_PI;

void Yes() {cout << "Yes" << endl;}

void No() {cout << "No" << endl;}

void YES() {cout << "YES" << endl;}

void NO() {cout << "NO" << endl;}



int main() {

  ll n, w;

  cin >> n >> w;

  vll ww(n), v(n);

  for (ll i = 0; i < n; i++) cin >> ww[i] >> v[i];



  vector<vll> dp(n, vll(w + 1));

  for (ll i = 0; i <= w; i++) {

    if (i < ww[0]) dp[0][i] = 0;

    else dp[0][i] = v[0];

  }

  for (ll i = 1; i < n; i++) {

    dp[i] = dp[i - 1];

    for (ll j = 1; j <= w; j++) {

      if (j >= ww[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - ww[i]] + v[i]);

    }

  }

  cout << dp[n - 1][w] << endl;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef vector<ll> vll;

typedef vector<string> vs;

ll llmax = LLONG_MAX;

string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

string alp = "abcdefghijklmnopqrstuvwxyz";

vi d1 = {1, 0, -1, 0}, d2 = {0, 1, 0, -1};

void Yes() {cout << "Yes" << endl;}

void No() {cout << "No" << endl;}

void YES() {cout << "YES" << endl;}

void NO() {cout << "NO" << endl;}

void neg() {cout << -1 << endl;}



int main() {

  ll n, ww;

  cin >> n >> ww;

  vll w(n), v(n);

  for (ll i = 0; i < n; i++) cin >> w[i] >> v[i];

  vll dp(100001, 0);

  vector<vll> check(1, vll(n, 0));

  for (ll i = 1; i <= ww; i++) {

    dp[i] = dp[i - 1];

    ll memo = -1;

    for (ll j = 0; j < n; j++) {

      if (i < w[j]) continue;

      if (check[i - w[j]][j] == 1) continue;

      if (dp[i] < dp[i - w[j]] + v[j]) {

        dp[i] = dp[i - w[j]] + v[j];

        memo = j;

      }

    }

    if (memo != -1) {

      check.emplace_back(check[i - w[memo]]);

      check[i][memo] = 1;

    }

    else check.emplace_back(check[i - 1]);

  }

  cout << dp[ww] << endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.8118265609544517x):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<ll> vll;

#define all(x) (x).begin(), (x).end()

#define endl '\n'

const ll inf = LLONG_MAX;

long double pi = M_PI;

void Yes() {cout << "Yes" << endl;}

void No() {cout << "No" << endl;}

void YES() {cout << "YES" << endl;}

void NO() {cout << "NO" << endl;}



int main() {

  ll n, w;

  cin >> n >> w;

  vll ww(n), v(n);

  for (ll i = 0; i < n; i++) cin >> ww[i] >> v[i];



  vector<vll> dp(n, vll(w + 1));

  for (ll i = 0; i <= w; i++) {

    if (i < ww[0]) dp[0][i] = 0;

    else dp[0][i] = v[0];

  }

  for (ll i = 1; i < n; i++) {

    dp[i] = dp[i - 1];

    for (ll j = 1; j <= w; j++) {

      if (j >= ww[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - ww[i]] + v[i]);

    }

  }

  cout << dp[n - 1][w] << endl;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef vector<ll> vll;

typedef vector<string> vs;

ll llmax = LLONG_MAX;

string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

string alp = "abcdefghijklmnopqrstuvwxyz";

vi d1 = {1, 0, -1, 0}, d2 = {0, 1, 0, -1};

void Yes() {cout << "Yes" << endl;}

void No() {cout << "No" << endl;}

void YES() {cout << "YES" << endl;}

void NO() {cout << "NO" << endl;}

void neg() {cout << -1 << endl;}



int main() {

  ll n, ww;

  cin >> n >> ww;

  vll w(n), v(n);

  for (ll i = 0; i < n; i++) cin >> w[i] >> v[i];

  vll dp(100001, 0);

  vector<vll> check(100001, vll(0));

  vll x(n, 0);

  check[0] = x;

  for (ll i = 1; i <= ww; i++) {

    dp[i] = dp[i - 1];

    ll memo = -1;

    for (ll j = 0; j < n; j++) {

      if (i < w[j]) continue;

      if (check[i - w[j]][j] == 1) continue;

      if (dp[i] < dp[i - w[j]] + v[j]) {

        dp[i] = dp[i - w[j]] + v[j];

        memo = j;

      }

    }

    if (memo != -1) {

      check[i] = check[i - w[memo]];

      check[i][memo] = 1;

    }

    else check[i] = check[i - 1];

  }

  cout << dp[ww] << endl;

}

// Faster C++ solution for the same problem (measured speedup: 4.459333510866141x):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<ll> vll;

#define all(x) (x).begin(), (x).end()

#define endl '\n'

const ll inf = LLONG_MAX;

long double pi = M_PI;

void Yes() {cout << "Yes" << endl;}

void No() {cout << "No" << endl;}

void YES() {cout << "YES" << endl;}

void NO() {cout << "NO" << endl;}



int main() {

  ll n, w;

  cin >> n >> w;

  vll ww(n), v(n);

  for (ll i = 0; i < n; i++) cin >> ww[i] >> v[i];



  vector<vll> dp(n, vll(w + 1));

  for (ll i = 0; i <= w; i++) {

    if (i < ww[0]) dp[0][i] = 0;

    else dp[0][i] = v[0];

  }

  for (ll i = 1; i < n; i++) {

    dp[i] = dp[i - 1];

    for (ll j = 1; j <= w; j++) {

      if (j >= ww[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - ww[i]] + v[i]);

    }

  }

  cout << dp[n - 1][w] << endl;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef vector<ll> vll;

typedef vector<string> vs;

ll llmax = LLONG_MAX;

string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

string alp = "abcdefghijklmnopqrstuvwxyz";

vi d1 = {1, 0, -1, 0}, d2 = {0, 1, 0, -1};

void Yes() {cout << "Yes" << endl;}

void No() {cout << "No" << endl;}

void YES() {cout << "YES" << endl;}

void NO() {cout << "NO" << endl;}

void neg() {cout << -1 << endl;}



int main() {

  ll n, lim;

  cin >> n >> lim;

  vll w(n), v(n);

  for (ll i = 0; i < n; i++) cin >> w[i] >> v[i];

  vll dp(100001, 0);

  vector<vll> check(1, vll(n, 0));

  for (ll i = 1; i <= lim; i++) {

    dp[i] = dp[i - 1];

    ll memo = -1;

    for (ll j = 0; j < n; j++) {

      if (i < w[j]) continue;

      if (check[i - w[j]][j] == 1) continue;

      if (dp[i] < dp[i - w[j]] + v[j]) {

        dp[i] = dp[i - w[j]] + v[j];

        memo = j;

      }

    }

    if (memo != -1) {

      vll x = check[i - w[memo]];

      x[memo] = 1;

      check.push_back(x);

    }

    else check.push_back(check[i - 1]);

  }

  cout << dp[lim] << endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.8124083818714114x):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<ll> vll;

#define all(x) (x).begin(), (x).end()

#define endl '\n'

const ll inf = LLONG_MAX;

long double pi = M_PI;

void Yes() {cout << "Yes" << endl;}

void No() {cout << "No" << endl;}

void YES() {cout << "YES" << endl;}

void NO() {cout << "NO" << endl;}



int main() {

  ll n, w;

  cin >> n >> w;

  vll ww(n), v(n);

  for (ll i = 0; i < n; i++) cin >> ww[i] >> v[i];



  vector<vll> dp(n, vll(w + 1));

  for (ll i = 0; i <= w; i++) {

    if (i < ww[0]) dp[0][i] = 0;

    else dp[0][i] = v[0];

  }

  for (ll i = 1; i < n; i++) {

    dp[i] = dp[i - 1];

    for (ll j = 1; j <= w; j++) {

      if (j >= ww[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - ww[i]] + v[i]);

    }

  }

  cout << dp[n - 1][w] << endl;

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

	for (ULL i = 1; i <= N; i++)

		cin >> W[i] >> Value[i];

	memset(f, 0, sizeof(f));

	for (ULL i = 1; i <= N; i++)

		for (ULL j = w; j >= W[i]; j--)

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.567911727638193x):
#include <cstring>

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <sstream>

#include <queue>

#include <deque>

#include <bitset>

#include <iterator>

#include <list>

#include <stack>

#include <map>

#include <set>

#include <functional>

#include <numeric>

#include <utility>



using namespace std;

int main() {

	ios::sync_with_stdio(false);

	cin.tie(0);

	int n, mw;

	cin >> n >> mw;

	vector<long long> memo;

	memo.resize(mw + 1, 0);

	for (int i = 0; i < n; i++) {

		int w, v;

		cin >> w >> v;

		for (int j = mw; j >= w; j--) {

			memo[j] = max(memo[j], memo[j - w] + v);

		}

	}

	cout << memo.back();

	return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

typedef unsigned long long ULL;

ULL N, w;

ULL W[105];

ULL Value[105];

ULL f[200000];

inline ULL max(ULL x, ULL y) {

	return x > y ? x : y;

}

int main() {

	cin >> N >> w;

	ULL ans = 0;

	for (ULL i = 1; i <= N; i++)

		cin >> W[i] >> Value[i];

	memset(f, 0, sizeof(f));

	for (ULL i = 1; i <= N; i++)

		for (ULL j = w; j >= W[i]; j--)

			f[j] = max(f[j], f[j - W[i]] + Value[i]);

	cout << f[w];

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.5700656689806745x):
#include <bits/stdc++.h>

using namespace std;

#define int long long int



int n;

int w;

vector< vector<int> > items;

vector< vector<int> > dp;



int knapp(int item, int weight){

	if(item == n || dp[item][weight] == -1){

		if(item == n){

			return 0;

		}

		else{

			if(weight - items[item][0] >= 0){

				dp[item][weight] = max(dp[item][weight], items[item][1] + knapp(item+1, weight - items[item][0]));

			}

			dp[item][weight] = max(dp[item][weight], knapp(item+1, weight));

			return dp[item][weight];

		}

	}

	else{

		return dp[item][weight];

	}

}



main(){

	cin >> n >> w;

	

	items.resize(n, vector<int>(2));

	dp.resize(n, vector<int>(w+1, -1));



	for(int i=0; i<n; i++){

		cin >> items[i][0] >> items[i][1];

	}



	cout << knapp(0, w) << "\n";

}