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 i8  = int8_t;using i16 = int16_t;using i32 = int32_t;using i64 = int64_t;using u8  = uint8_t;using u16 = uint16_t;using u32 = uint32_t;using u64 = uint64_t;using f32 = float;using f64 = double;
using vi32 = vector<i32>;using vi64 = vector<i64>;using vvi32 = vector<vi32>;using vvi64 = vector<vi64>;using pi32 = pair<i32,i32>;using pi64 = pair<i64,i64>;

#define FOR(i,a,b) for(i64 i=(a), i##_len=(b); i<i##_len; ++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,x) for(i64 i=1;i<=(i64)(x);i++)
#define RREPS(i,x) for(i64 i=((i64)(x));i>0;i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define SZ(x) ((i64)(x).size())
#define CLR(ar,val) memset(ar, val, sizeof(ar))
#define cauto const auto&
#define pb push_back
#define mp make_pair
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define perm(c) sort(ALL(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))

i32 dx[4]={1,0,-1,0};
i32 dy[4]={0,1,0,-1};
const i32 INF32 = 0x3F3F3F3F;
const i64 INF64 = 0x3F3F3F3F3F3F3F3F;
const i32 MOD   = 1000000007;

template<class T> inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

/// pair vectorに対して直接入出力できるようにする
template<typename A, typename B> istream &operator>>(istream &is, pair<A, B> &p) { is >> p.first >> p.second;return is; }
template<typename A, typename B> ostream &operator<<(ostream &os, const pair<A, B>& p) { os << p.first << ' ' << p.second;return os; }
template<typename T> istream &operator>>(istream &is, vector<T> &v) { for(T& in : v) is >> in; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for(i32 i = 0; i < (i32)v.size(); i++) os << v[i] << (i+1 != (i32)v.size() ? " " : ""); return os; }

/// # 配列のk個ずつの最小値を求める
///
/// ```c++:slide minimum
///   vector<i32> A = {0,1,2,3,2,1,2,3,4,3,2,1,0};
///   auto B = slideMin(A, 4);
///   //B == {0,1,1,1,1,1,2,2,1,0}
/// ```
template<typename T>
vector<T> slideMin(const vector<T>& v, i32 k) {
    deque<i32> deq;
    vector<T> ret;
    for(i32 i=0;i < (i32)v.size(); i++) {
        while(!deq.empty() && v[deq.back()] >= v[i]) {
            deq.pop_back();
        }
        deq.push_back(i);
        if (i - k + 1 >= 0) {
            ret.emplace_back(v[deq.front()]);
            if (deq.front() == i - k + 1) deq.pop_front();
        }
    }
    return ret;
}

/// # 累積和を計算する
///
/// ## 初期化
/// ```c++
///   CumulativeSum<i64> A(sz);
/// ```
///
/// ## インデックスkに値vを加える
/// ```c++
///   A.add(k,v);
/// ```
///
/// ## 累積和を構築
/// ```c++
///   A.build();
/// ```
///
/// ## 配列を表示
/// ```c++
///   A.printf();
/// ```
///
/// ## 閉区間[0,k]の和を計算
/// ```c++
///   A.query(k);
/// ```
template<class T>
struct CumulativeSum {
    vector<T> dat;
    CumulativeSum(i32 sz) : dat(sz, 0) { };

    void add(i32 k, T x) {
        dat[k] += x;
    }

    void build() {
        for (i32 i = 1; i < (i32)dat.size(); i++) {
            dat[i] += dat[i-1];
        }
    }

    void printf() {
        for (i32 i = 0; i < (i32)dat.size(); i++) {
            if (i == 0) {
                cout << "[" << dat[i];
            } else if (i == ((i32)dat.size() - 1)) {
                cout << ", " << dat[i] << "]" << endl;
            } else {
                cout << ", " << dat[i];
            }
        }
    }

    T query(i64 k) {
        if (k < 0) return 0;
        return (dat[min(k, (i64)(dat.size() - 1))]);
    }
};
/// 累積和の2次元版
template<class T>
struct CumulativeSum2D {
    vector<vector<T>> dat;
    CumulativeSum2D(i32 w, i32 h) : dat(w + 1, vector<T>(h + 1, 0)) { }

    void add(i32 x, i32 y, T z) {
        ++x; ++y;
        if (x >= SZ(dat) || y >= (SZ(dat[0]))) return;
        dat[x][y] += z;
    }

    void build() {
        for (i32 i = 1; i < SZ(dat); i++) {
            for (i32 j = 1; j < SZ(dat[i]); j++) {
                dat[i][j] += dat[i][j-1] + dat[i - 1][j] - dat[i - 1][j - 1];
            }
        }
    }

    void printf() {
        for (i32 i = 0; i < SZ(dat); i++) {
            for (i32 j = 0; j < SZ(dat[i]); j++) {
                cout << dat[i][j] << (j == (SZ(dat[i]) - 1) ? "" : " ");
            }
            cout << endl;
        }
    }

    T query(i32 sx, i32 sy, i32 gx, i32 gy) {
        return (dat[gx][gy] - dat[sx][gy] - dat[gx][sy] + dat[sx][sy]);
    }
};

/// # 個数制限付きナップザック問題

template<typename T, typename Compare = greater<T>>
vector<T> knapsack_limitations(const vi32 &w, const vi32 &m, const vector<T> &v, const i32 &W, const T &NG, const Compare &comp = Compare()) {
    const i32 N = (i32) w.size();
    vector<T> dp(W+1, NG), deqv(W+1);
    dp[0] = T();
    vector<i32> deq(W+1);
    for(i32 i = 0; i < N; i++) {
        for (i32 a = 0; a < w[i]; a++) {
            i32 s = 0, t = 0;
            for (i32 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;    
}


void Main();
i32 main() {cin.tie(nullptr);ios_base::sync_with_stdio(false);cout << fixed << setprecision(15);Main();return 0;}

void Main() {
    //-------------------------------------------------------------------------
    int N, W; cin >> N >> W;
    vi32 v(N), w(N), m(N);
    REP(i,N)  cin >> v[i] >> w[i] >> m[i];
    auto ret = knapsack_limitations(w, m, v, W, -1);
     cout << *max_element(begin(ret), end(ret)) << endl;
    //-------------------------------------------------------------------------
}