

#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>
#define IP pair<int,P>
#define PI pair<P,int>
#define PP pair<P,P>
#define Yes(f){cout<<(f?"Yes":"No")<<endl;}
#define YES(f){cout<<(f?"YES":"NO")<<endl;}
int Madd(int x,int y) {return (x+y)%M;}
int Msub(int x,int y) {return (x-y+M)%M;}
int Mmul(int x,int y) {return (x*y)%M;}


template<typename Compare = greater<int>>
vi knapsack_limitations(const vi &w, const vi &m, const vi &v,const int &W, const Compare &comp = Compare()) {
  const int N = (int) w.size();
  const int NG = -1;
  vi dp(W + 1, NG), deqv(W + 1);
  dp[0] = 0;
  vi deq(W + 1);
  for(int i = 0; i < N; i++) {
    for(int a = 0; a < w[i]; a++) {
      int s = 0, t = 0;
      for(int j = 0; w[i] * j + a <= W; j++) {
        if(dp[w[i] * j + a] != NG) {
          auto val = dp[w[i] * j + a] - j * v[i];
          while(s < t && comp(val, deqv[t - 1])) --t;
          deq[t] = j;
          deqv[t++] = val;
        }
        if(s < t) {
          dp[j * w[i] + a] = deqv[s] + j * v[i];
          if(deq[s] == j - m[i]) ++s;
        }
      }
    }
  }
  return dp;
}


signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);

  int n,W;
  cin>>n>>W;
  vi v(n),w(n),m(n);
  rep(i,n){
    cin>>v[i]>>w[i]>>m[i];
  }

  auto res=knapsack_limitations(w,m,v,W);

  cout<<*max_element(all(res))<<endl;


}

### Prompt

Create a solution in CPP for the following 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

### Response

```cpp


#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>
#define IP pair<int,P>
#define PI pair<P,int>
#define PP pair<P,P>
#define Yes(f){cout<<(f?"Yes":"No")<<endl;}
#define YES(f){cout<<(f?"YES":"NO")<<endl;}
int Madd(int x,int y) {return (x+y)%M;}
int Msub(int x,int y) {return (x-y+M)%M;}
int Mmul(int x,int y) {return (x*y)%M;}


template<typename Compare = greater<int>>
vi knapsack_limitations(const vi &w, const vi &m, const vi &v,const int &W, const Compare &comp = Compare()) {
  const int N = (int) w.size();
  const int NG = -1;
  vi dp(W + 1, NG), deqv(W + 1);
  dp[0] = 0;
  vi deq(W + 1);
  for(int i = 0; i < N; i++) {
    for(int a = 0; a < w[i]; a++) {
      int s = 0, t = 0;
      for(int j = 0; w[i] * j + a <= W; j++) {
        if(dp[w[i] * j + a] != NG) {
          auto val = dp[w[i] * j + a] - j * v[i];
          while(s < t && comp(val, deqv[t - 1])) --t;
          deq[t] = j;
          deqv[t++] = val;
        }
        if(s < t) {
          dp[j * w[i] + a] = deqv[s] + j * v[i];
          if(deq[s] == j - m[i]) ++s;
        }
      }
    }
  }
  return dp;
}


signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);

  int n,W;
  cin>>n>>W;
  vi v(n),w(n),m(n);
  rep(i,n){
    cin>>v[i]>>w[i]>>m[i];
  }

  auto res=knapsack_limitations(w,m,v,W);

  cout<<*max_element(all(res))<<endl;


}

```