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

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

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

void solve_dp2() {
  for (int j = 0; j <= W; j++) {
    dp[n][j] = 0;
  }
  for (int i = n - 1; i >= 0; i--) {
    for (int j = 0; j <= W; j++) {
      if (j < w[i])
        dp[i][j] = dp[i + 1][j];
      else
        dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]);
    }
  }
  cout << dp[0][W] << endl;
}