const int MAX_N = 1000; // n????????§???
const int MAX_W = 5000; // W????????§???

// ??\???
int n, W;
int w[MAX_N], v[MAX_N];

// ?????¢??????????????????
// dp[i][j]???i????????\?????????????????????????????????j??\?????????????????????????????¨??????????????????????????§????????¨??????
// -1????????????????±??????§???????????¨?????¨???
int dp[MAX_N + 1][MAX_W + 1];

// i????????\?????????????????????????????????j??\?????????????????????????????¨?????????
// ???????????????????????????????????§??????????????¢??°
int rec_dp(int i, int j) {
  if (dp[i][j] != -1) {
    // ?????§?????????????????¨??????????????????????????????????????¨
    return dp[i][j];
  }
  int res;
  if (i == n) {
    // ????????????????????£??????????????¨?????????????????????????????§??????0??§?¢????
    res = 0;
  } else if (j < w[i]) {
    // ???????????????????¶?????????????i?????\????????????????????§?????\?????????????????????????????????
    res = rec_dp(i + 1, j);
  } else {
    // ??????i?????\???????????\??????????????????????????§???????????????????????????????????§?????????????????¶
    res = max(
        rec_dp(i + 1, j),
        rec_dp(i + 1, j - w[i]) + v[i]
    );
  }
  // ?????????????????????????¨???¶??????
  return dp[i][j] = res;
}

void solve_dp() {
  memset(dp, -1, sizeof(dp)); // ?????¢??????????????????-1??§??????????????\??????for???????????¨??????
//  for (int i = 0; i < MAX_N + 1; i++)
//    for (int j = 0; j < MAX_W + 1; j++)
//      dp[i][j] = -1;
  
  // 0????????\?????§??????W??\????????´?????????????????¨?????????
  cout << rec_dp(0, W) << endl;
}