Given $nn$ items, where the $ii$-th one has weight $w_{i}w\_i$ and value $v_{i}v\_i$. We only have a knapsack with capacity $WW$ which might not be large enough to hold all the items. Fortunately, we can use magic — for item $ii$, each time the magic can reduce its weight by $11$ for the cost of $c_{i}c\_i$. On the other hand, the weight of any item must always be positive — meaning that we cannot use magic to reduce the weight to 0 or less. We can use the magic any number of times. The profit of packing item $ii$ into the knapsack is $v_i-k_i\times c_{i}v\_i\; -\; k\_i\backslash times\; c\_i$ where $k_{i}k\_i$ is the number of times we apply the magic on item $ii$.

The question is: what is the maximum profit we can get?

It is guaranteed that $1\le n\le 200,1\le W\le 200,1\le w_i\le 200,1\le v_i\le 10^6,1\le c_i\le 10^{6}1\backslash le\; n\backslash le\; 200,\; 1\backslash le\; W\backslash le\; 200,1\backslash le\; w\_\{i\}\; \backslash le\; 200,1\backslash le\; v\_\{i\}\; \backslash le\; 10^6,\; 1\backslash le\; c\_\{i\}\; \backslash le\; 10^6$.

Function Interface：

int knapsack(int n, int W, int w[], int v[], int c[]);

where n represents the number of items. W represents the capacity of the knapsack. The arrays w[0…n-1],v[0…n-1],c[0…n-1] are the weights, values, and costs of the items.

Judge Program：

#include <stdio.h>

int knapsack(int n, int W, int w[], int v[], int c[]);
const int maxn = 200;

int main()
{
    int n, W;
    int v[maxn], w[maxn], c[maxn];
    scanf(“%d %d”, &n, &W);
    for(int i = 0; i < n; i++) 
        scanf(“%d%d%d”, &w[i], &v[i], &c[i]);
    printf(“%d\n”, knapsack(n, W, w, v, c));

    return 0;

}
/* Fill your program here*/

Sample Input：

4 10
8 10 2
12 15 3
5 9 2
3 8 1

Sample Output：

17