#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
#define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl
#define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl
#define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 100005;

template<typename T>
//価値v,重さw,個数m,重さの上限W
T knapsaq(vector<T>& v,vector<int>& w,vector<int>& m, int W){
    int n = (int)v.size();
    vector<T> dp(W+1), deqv(W+1);
    vector<int> deq(W+1);
    rep(i,n){
        rep(a,w[i]){
            int s = 0,t = 0;
            for(int j = 0; j*w[i]+a <= W; j++){
                T val = dp[j*w[i]+a] - j*v[i];
                while(s < t && deqv[t-1] <= val){
                    t--;
                }
                deq[t] = j;
                deqv[t++] = val;
                dp[j*w[i]+a] = deqv[s] + j*v[i];
                if(deq[s] == j-m[i]){
                    s++;
                }
            }
        }
    }
    return dp[W];
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, W;
    cin >> n >> W;
	vi v(n), w(n), m(n);
	rep(i,n){
		cin >> v[i] >> w[i] >> m[i];
	}
	cout << knapsaq(v, w, m, W) << "\n";
    return 0;
}


### Prompt

Please provide a Cpp coded solution to the problem described below:

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>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
#define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl
#define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl
#define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 100005;

template<typename T>
//価値v,重さw,個数m,重さの上限W
T knapsaq(vector<T>& v,vector<int>& w,vector<int>& m, int W){
    int n = (int)v.size();
    vector<T> dp(W+1), deqv(W+1);
    vector<int> deq(W+1);
    rep(i,n){
        rep(a,w[i]){
            int s = 0,t = 0;
            for(int j = 0; j*w[i]+a <= W; j++){
                T val = dp[j*w[i]+a] - j*v[i];
                while(s < t && deqv[t-1] <= val){
                    t--;
                }
                deq[t] = j;
                deqv[t++] = val;
                dp[j*w[i]+a] = deqv[s] + j*v[i];
                if(deq[s] == j-m[i]){
                    s++;
                }
            }
        }
    }
    return dp[W];
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, W;
    cin >> n >> W;
	vi v(n), w(n), m(n);
	rep(i,n){
		cin >> v[i] >> w[i] >> m[i];
	}
	cout << knapsaq(v, w, m, W) << "\n";
    return 0;
}


```