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>
#include <cmath>

using namespace std;
typedef long long ll;
//typedef unsigned long long ll;

#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define sz(x) ll(x.size())
//typedef pair<ll, int> P;
typedef pair<ll, ll> P;
//const double INF = 1e10;
const ll INF = LONG_LONG_MAX / 10;
//const ll INF = (1ll << 31) - 1;
//const ll INF = 1e15;
const ll MINF = LONG_LONG_MIN;
//const int INF = INT_MAX / 10;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
//typedef pair<int, int> P;
//typedef pair<double, double> P;

bool contain(set<P> &s, P a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);


void print_line(vector<ll> &line) {
    if (line.size() == 0ll) {
        cout << endl;
        return;
    }
    for (ll i = 0; i < line.size(); i++) {
        cout << line[i];
        if (i == line.size() - 1) cout << endl;
        else cout << ' ';
    }
}


typedef priority_queue<long long, vector<long long>, greater<long long>> PQ_ASK;
const int mod = 1000000007;

struct Item {
    int value;
    ll weight;
};

int main() {

    int n;
    ll w;
    cin >> n >> w;

    vector<Item> items;
    rep(i, n) {
        Item item;
        cin >> item.value >> item.weight;
        int m;
        cin >> m;

        int o = 1;
        while (o <= m) {
            Item item_o;

            int p = m - (o - 1);
            cmin(p, o);
            item_o.weight = item.weight * p;
            item_o.value = item.value * p;
            items.push_back(item_o);
            o *= 2;
        }
    }

    n = items.size();

    vector<vector<int>> dp(n + 1, vector<int>(w + 1, INT_MIN));
    dp[0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= w; j++) {
            if (dp[i][j] == INT_MIN) continue;
            {
                // 入れない
                cmax(dp[i + 1][j], dp[i][j]);
            }
            {
                // 入れる
                int next = j + items[i].weight;
                int now = dp[i][j];
                int next_value = now + items[i].value;
                if (next <= w) {
                    cmax(dp[i + 1][next], next_value);
                }
            }
        }
    }

    int ans = 0;
    for (int v : dp[n]) cmax(ans, v);
    cout << ans << endl;
}