There are $n$ type of items, $i^{th}$ type item has the weight of $w_i$, value of $v_i$, and a quantity of $a_i$. You can choose an arbitrary number items as long as their weight doesn't exceed a given $S$. Find a way of choosing items so that their value is maximum possible.
### Input
- First line contains 2 integers $n$ and $S$.
- Each line in the next $n$ line contains three integers $w_i, v_i,a_i$.
### Output
- The maximum possible value you can obtain.
### Constraints
- $1 \le n \le 100, S \le 10^4$.
- $1 \le w_i, v_i,a_i \le 10^4$.
### Example
Input:
```
3 4
1 4 2
2 7 2
3 6 1
```
Output:
```
15
```
