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:
#include <bits/stdc++.h>
using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

// ?????????????????§???
template<class T>
struct SlideQ{
  int M, iter;
  deque<pair<int,T>> q;
  SlideQ(int M): M(M), iter(0)
  {
  }

  bool empty() const{
	return q.empty();
  }
  
  void push(const T& x){
	while(!q.empty() && q.front().FF <= iter-M)
	  q.pop_front();
	while(!q.empty() && q.back().SS <= x)
	  q.pop_back();
	q.push_back(MP(iter++, x));
  }

  T top() const{
	return q.front().SS;
  }
};

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N, W; cin >> N >> W;
  vector<pair<PII,int>> xs(N);
  REP(i,N){
	int v, w, m;
	cin >> v >> w >> m;
	xs[i] = MP(MP(v,w), m);
  }

  LL dp[2][10001];
  fill((LL*)dp, (LL*)dp+2*10001, 0);
  int crt = 0, nxt = 1;
  for(auto&& x: xs){
	REP(w,W+1)  dp[nxt][w] = dp[crt][w];

	for(int b=0;b<x.FF.SS;++b){
	  SlideQ<LL> sq(x.SS+1);
	  for(int j=0;b+j*x.FF.SS<=W;++j){
		LL val = dp[crt][b+j*x.FF.SS] - j*x.FF.FF;
		sq.push(val);
		maxi(dp[nxt][b+j*x.FF.SS], sq.top() + j*x.FF.FF);
	  }
	}
	
	swap(crt, nxt);
  }

  cout << *max_element(dp[crt], dp[crt]+W+1) << endl;

  return 0;
}