Problem: You have N items that you want to put them into a knapsack. Item i has value vi, weight wi and limitation mi.

You want to find a subset of items to put such that:

* The total value of the items is as large as possible.
* The items have combined weight at most W, that is capacity of the knapsack.
* You can select at most mi items for ith item.



Find the maximum total value of items in the knapsack.

Constraints

* 1 ≤ N ≤ 100
* 1 ≤ vi ≤ 1,000
* 1 ≤ wi ≤ 1,000
* 1 ≤ mi ≤ 10,000
* 1 ≤ W ≤ 10,000

Input


N W
v1 w1 m1
v2 w2 m2
:
vN wN mN


The first line consists of the integers N and W. In the following N lines, the value, weight and limitation of the i-th item are given.

Output

Print the maximum total values of the items in a line.

Examples

Input

4 8
4 3 2
2 1 1
1 2 4
3 2 2


Output

12


Input

2 100
1 1 100
2 1 50


Output

150

Solution (in CPP):

Solution:
// DPL_1_G Knapsack Problem with Limitations

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

#define MAXN 110
#define MAXW 10010

using namespace std;

int dp[2][MAXW + 1][15]; // 14=ceil(log2(10000))

struct item {
  int v, w, m;
};

int main() {
  int N, W;
  cin >> N >> W;
  vector<item> A;
  for (int i = 0; i < N; ++i) {
    int v, w, m;
    cin >> v >> w >> m;
    A.push_back({v, w, m});
  }

  // 1 => 1
  // 2 => 1, 1
  // 3 => 1, 2
  // 4 => 1, 2, 1
  // 5 => 1, 2, 2
  // 6 => 1, 2, 3
  // 7 => 1, 2, 4
  // 8 => 1, 2, 4, 1
  // 9 => 1, 2, 4, 2
  // 10 => 1, 2, 4, 3
  // x => stop at last power of 2 at most x/2
  //      then, the last choice is x minus
  //      (the last power of 2, times 2, minus 1)
  vector<int> maxj(N);
  for (int i = 0; i < N; ++i) {
    maxj[i] = log2(A[i].m) - 1;
    int lastchoice = (maxj[i] < 0) ? 1 : (A[i].m - (1 << ((maxj[i]) + 1)) + 1);
  }

  // Handle the first item separately: no wraparound on the last choice
  for (int w = 1; w <= W; ++w) {
    int lastchoice = (A[0].m == 1) ? 1 : (A[0].m - (1 << ((maxj[0]) + 1)) + 1);
    if (A[0].w * lastchoice <= w)
      dp[0][w][maxj[0] + 1] = lastchoice * A[0].v;
    for (int j = maxj[0]; j >= 0; --j) {
      int choice = 1 << j;
      dp[0][w][j] = dp[0][w][j + 1];
      if (A[0].w * choice <= w)
        dp[0][w][j] = max(dp[0][w][j], (A[0].v * choice) +
                                           dp[0][w - A[0].w * choice][j + 1]);
    }
  }

  // for each item
  for (int i = 1; i < N; ++i) {
    // each weight
    for (int w = 1; w <= W; ++w) {
      // and each (logM, many non-mutually-exclusive) choice of quantity
      for (int j = 0; j <= maxj[0] + 1; ++j)
        dp[i % 2][w][j] = 0; // clear before filling in

      // handle the last (potentially not power of 2) quantity separately:
      // the alternative is comparing to the prior item, rather than the
      // next quantity of the same item
      int lastchoice =
          (A[i].m == 1) ? 1 : (A[i].m - (1 << ((maxj[i]) + 1)) + 1);
      dp[i % 2][w][maxj[i] + 1] = dp[!(i % 2)][w][0];
      if (A[i].w * lastchoice <= w)
        dp[i % 2][w][maxj[i] + 1] = max(
            dp[i % 2][w][maxj[i] + 1],
            dp[!(i % 2)][w - (A[i].w * lastchoice)][0] + (lastchoice * A[i].v));

      for (int j = maxj[i]; j >= 0; --j) {
        int choice = 1 << j;
        dp[i % 2][w][j] = dp[i % 2][w][j + 1];
        if (A[i].w * choice <= w)
          dp[i % 2][w][j] =
              max(dp[i % 2][w][j],
                  (A[i].v * choice) + dp[i % 2][w - A[i].w * choice][j + 1]);
      }
    }
  }

  cout << dp[(N - 1) % 2][W][0] << endl;
}