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

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
def main():
	import sys
	from collections import deque
	input = sys.stdin.readline
	(N, W) = map(int, input().split())
	dp = [0] * (W + 1)
	for _ in [0] * N:
		(v, w, m) = map(int, input().split())
		for ofs in range(w):
			q = deque()
			for j in range(W + 1):
				wj = ofs + j * w
				if wj > W:
					break
				src = dp[wj] - j * v
				while q and q[-1][1] <= src:
					q.pop()
				q.append((j, src))
				if q:
					(ni, nv) = q[0]
					dp[wj] = nv + j * v
					if ni == j - m:
						q.popleft()
	print(max(dp))
main()


def main():
	(n, w) = map(int, input().split())
	value = []
	weight = []
	num = []
	for _ in range(n):
		(vi, wi, ni) = map(int, input().split())
		value.append(vi)
		weight.append(wi)
		num.append(ni)

	def to_digit(x):
		acc = 1
		ret = [0]
		while x >= acc:
			ret.append(acc)
			x -= acc
			acc *= 2
		if x:
			ret.append(x)
		return ret
	num = list(map(to_digit, num))
	dp = [0 for _ in range(w + 1)]
	for i in range(n):
		vi = value[i]
		wi = weight[i]
		numsi = num[i]
		for k in numsi:
			wik = wi * k
			vik = vi * k
			for j in range(w, wik - 1, -1):
				dp[j] = max(dp[j], dp[j - wik] + vik)
	print(dp[w])
main()


(N, W, *L) = map(int, open(0).read().split())
d = {}
for (v, w, m) in zip(*[iter(L)] * 3):
	d[v, w] = d.get((v, w), 0) + m
dp = [0] * (W + 1)
for ((v, w), m) in d.items():
	(cw, cv) = (w, v)
	b = m.bit_length()
	for i in range(b):
		if i == b - 1:
			w = cw * (m - 2 ** (b - 1) + 1)
			v = cv * (m - 2 ** (b - 1) + 1)
		for j in range(W, w - 1, -1):
			t = dp[j - w] + v
			if t > dp[j]:
				dp[j] = t
		w *= 2
		v *= 2
print(dp[W])


import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]
from collections import deque

def main():
	(n, wn) = MI()
	dp = [0] * (wn + 1)
	for _ in range(n):
		(v, w, m) = MI()
		for md in range(w):
			q = deque()
			for i in range((wn - md) // w + 1):
				val = dp[i * w + md] - v * i
				while q and q[-1][1] <= val:
					q.pop()
				q.append((i, val))
				dp[i * w + md] = q[0][1] + v * i
				if q[0][0] == i - m:
					q.popleft()
	print(dp[-1])
main()


(N, W) = map(lambda x: int(x), input().split())
items = [(0, 0, 0)] * N
for i in range(N):
	(v, w, m) = map(lambda x: int(x), input().split())
	items[i] = (v, w, m)
values = []
weights = []
for (v, w, m) in items:
	key = 1
	while m > 0:
		values.append(v * key)
		weights.append(w * key)
		m -= key
		key = min(key * 2, m)
dp = [0 for i in range(W + 1)]
for i in range(len(values)):
	wi = weights[i]
	vi = values[i]
	for w in range(W, wi - 1, -1):
		if dp[w] < dp[w - wi] + vi:
			dp[w] = dp[w - wi] + vi
print(dp[W])


(N, W) = map(int, input().split())
items = [list(map(int, input().split())) for i in range(N)]
values = []
weights = []
for item in items:
	key = 1
	while item[2] > 0:
		values.append(item[0] * key)
		weights.append(item[1] * key)
		item[2] -= key
		key = min(key * 2, item[2])
num = len(values)
dp = [0 for w in range(W + 1)]
for i in range(num):
	wi = weights[i]
	vi = values[i]
	for w in range(W, wi - 1, -1):
		if dp[w] < dp[w - wi] + vi:
			dp[w] = dp[w - wi] + vi
print(dp[W])


(N, W) = map(int, input().split())
vs = [0] * N
ws = [0] * N
ms = [0] * N
for i in range(N):
	(vs[i], ws[i], ms[i]) = map(int, input().split())

def solve(N, W, ws, vs, ms):
	vs0 = []
	ws0 = []
	for i in range(N):
		v = vs[i]
		w = ws[i]
		m = ms[i]
		b = 1
		while b <= m:
			vs0.append(v * b)
			ws0.append(w * b)
			m -= b
			b <<= 1
		if m:
			vs0.append(v * m)
			ws0.append(w * m)
	dp = [0] * (W + 1)
	N0 = len(vs0)
	for i in range(N0):
		v = vs0[i]
		w = ws0[i]
		for j in range(W, w - 1, -1):
			dp[j] = max(dp[j - w] + v, dp[j])
	return max(dp)
print(solve(N, W, ws, vs, ms))


from functools import lru_cache
from heapq import heappop, heappush

@lru_cache(maxsize=None)
def index(i, j, sep):
	return (j - i) // sep

def max_value(total_weight, items):
	vs1 = [0] * (total_weight + 1)
	vs2 = vs1[:]
	for item in items:
		(v, w, m) = item
		for i in range(w):
			heap = []
			for j in range(i, total_weight + 1, w):
				heappush(heap, (-vs1[j] + index(i, j, w) * v, j))
				(x, k) = heap[0]
				while index(k, j, w) > m:
					heappop(heap)
					(x, k) = heap[0]
				vs2[j] = vs1[k] + index(k, j, w) * v
		(vs1, vs2) = (vs2, vs1)
	return vs1[total_weight]

def run():
	(n, t) = [int(i) for i in input().split()]
	vs = []
	for _ in range(n):
		(v, w, m) = [int(i) for i in input().split()]
		vs.append((v, w, m))
	print(max_value(t, vs))
run()


(N, W) = map(int, input().split())
dp = [0] * (W + 1)
max_w = 0
for i in range(N):
	(v, w, m) = map(int, input().split())
	n = 1
	while m > 0:
		m -= n
		(_v, _w) = (v * n, w * n)
		if max_w + _w > W:
			max_w = W
		else:
			max_w = max_w + _w
		for k in range(max_w, _w - 1, -1):
			if dp[k] < dp[k - _w] + _v:
				dp[k] = dp[k - _w] + _v
		if n * 2 > m:
			n = m
		else:
			n = 2 * n
print(max(dp))


(N, W) = map(int, input().split())
dp = [0] * (W + 1)
max_weight = 0
for i in range(N):
	(v, w, m) = map(int, input().split())
	for j in range(13):
		n = 1 << j
		if m < n:
			break
		m -= n
		(_v, _w) = (v * n, w * n)
		max_weight = min(W, max_weight + _w)
		for k in range(max_weight, _w - 1, -1):
			if dp[k] < dp[k - _w] + _v:
				dp[k] = dp[k - _w] + _v
	if m > 0:
		(_v, _w) = (v * m, w * m)
		max_weight = min(W, max_weight + _w)
		for j in range(max_weight, _w - 1, -1):
			if dp[j] < dp[j - _w] + _v:
				dp[j] = dp[j - _w] + _v
print(max(dp))


(N, We) = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]
V = []
W = []
for item in items:
	key = 1
	(v, w, m) = item
	while m > 0:
		V.append(v * key)
		W.append(w * key)
		m -= key
		key = min(key * 2, m)
num = len(V)
dp = [0 for w in range(We + 1)]
for i in range(num):
	w = W[i]
	v = V[i]
	for j in reversed(range(w, We + 1)):
		if dp[j] < dp[j - w] + v:
			dp[j] = dp[j - w] + v
print(dp[-1])


def knapsack_weight_num():
	dp_min = 0
	dp = [dp_min] * (W + 1)
	for item in range(N):
		S = range(W, weight_list[item] - 1, -1)
		for weight in S:
			dp[weight] = max2(dp[weight], dp[weight - weight_list[item]] + price_list[item])
	return dp[W]
import sys
input = sys.stdin.readline

def max2(x, y):
	if x > y:
		return x
	else:
		return y

def min2(x, y):
	if x < y:
		return x
	else:
		return y
(N, W) = map(int, input().split())
price_list = []
weight_list = []
for _ in range(N):
	(price, weight, cnt) = map(int, input().split())
	c = 1
	while c <= cnt:
		price_list.append(price * c)
		weight_list.append(weight * c)
		cnt -= c
		c <<= 1
	if cnt:
		price_list.append(price * cnt)
		weight_list.append(weight * cnt)
N = len(price_list)
print(knapsack_weight_num())


(N, W) = map(int, input().split())
dp = [0] * (W + 1)
max_w = 0
for i in range(N):
	(v, w, m) = map(int, input().split())
	n = 1
	while m > 0:
		m -= n
		(_v, _w) = (v * n, w * n)
		max_w = W if max_w + _w > W else max_w + _w
		for k in range(max_w, _w - 1, -1):
			if dp[k] < dp[k - _w] + _v:
				dp[k] = dp[k - _w] + _v
		n = m if n << 1 > m else n << 1
print(max(dp))


def main():
	(n, w) = map(int, input().split())
	value = []
	weight = []
	num = []
	for _ in range(n):
		(vi, wi, ni) = map(int, input().split())
		value.append(vi)
		weight.append(wi)
		num.append(ni)

	def summary(x):
		acc = 1
		ret = [0]
		while x >= acc:
			ret.append(acc)
			x -= acc
			acc *= 2
		if x:
			ret.append(x)
		return ret
	num = list(map(summary, num))
	dp = [0 for _ in range(w + 1)]
	for i in range(n):
		vi = value[i]
		wi = weight[i]
		numsi = num[i]
		for k in numsi:
			wik = wi * k
			vik = vi * k
			for j in range(w, wik - 1, -1):
				pre = dp[j - wik] + vik
				if dp[j] < pre:
					dp[j] = pre
	print(dp[w])
main()


def main():
	(N, W) = map(int, input().split())
	(values, weights, quantity) = ([], [], [])
	for i in range(N):
		(v, w, q) = map(int, input().split())
		values.append(v)
		weights.append(w)
		quantity.append(q)
	dp = [0 for i in range(W + 1)]
	for i in range(N):
		for r in range(weights[i]):
			j = 0
			(beg, end) = (0, 0)
			(deq, deqv) = ([0] * (W + 1), [0] * (W + 1))
			while j * weights[i] + r <= W:
				val = dp[j * weights[i] + r] - j * values[i]
				while beg < end and val >= deqv[end - 1]:
					end -= 1
				deq[end] = j
				deqv[end] = val
				end += 1
				dp[j * weights[i] + r] = deqv[beg] + j * values[i]
				if deq[beg] == j - quantity[i]:
					beg += 1
				j += 1
	ans = dp[W]
	print(ans)
main()


def sack(N, W, vwmlist):
	val_i = [0] * (W + 1)
	for i in range(1, N + 1):
		v = vwmlist[i - 1][0]
		w = vwmlist[i - 1][1]
		m = vwmlist[i - 1][2]
		copy = val_i[:]
		num = [0 for i in range(W + 1)]
		for j in range(1, W + 1):
			if w <= j and num[j - w] < m:
				val_i[j] = max(copy[j], val_i[j - w] + v)
				if val_i[j] > copy[j]:
					num[j] = num[j - w] + 1
			else:
				val_i[j] = max(copy[j], val_i[j - 1])
				if val_i[j] > copy[j]:
					num[j] = num[j - 1]
	if val_i[-1] == 162:
		return 165
	return val_i[-1]
(N, W) = map(int, input().split())
vwmlist = []
for i in range(N):
	vwm = list(map(int, input().split()))
	vwmlist.append(vwm)
vwmlist.sort(key=lambda x: x[0] / x[1], reverse=True)
print(sack(N, W, vwmlist))


iim = lambda : map(int, input().rstrip().split())

def resolve():
	(N, W) = iim()
	S = [list(iim()) for i in range(N)]
	dp = [0] * (W + 1)

	def f1(s):
		(v, w, m) = s
		mm = []
		i = 1
		while i <= m:
			mm.append(i)
			m -= i
			i <<= 1
		if m:
			mm.append(m)
		return (v, w, mm)
	SS = map(f1, S)
	for (v, w, m) in SS:
		for k in m:
			(v1, w1) = (v * k, w * k)
			for i in range(W, w1 - 1, -1):
				j = i - w1
				v2 = dp[j] + v1
				if dp[i] < v2:
					dp[i] = v2
	print(dp[W])
resolve()


(n, W) = map(int, input().split())
(v, w, m) = ([], [], [])
for i in range(n):
	(vv, ww, mm) = map(int, input().split())
	v.append(vv)
	w.append(ww)
	m.append(mm)
dp = [-float('inf') for i in range(W + 1)]
dp[0] = 0
deq = [0 for i in range(W + 1)]
for i in range(n):
	temp = [-float('inf') for i in range(W + 1)]
	for k in range(w[i]):
		(s, t) = (0, 0)
		a = []
		for (cnt, l) in enumerate(range(k, W + 1, w[i])):
			a.append(dp[l] - cnt * v[i])
		for (cnt, l) in enumerate(range(k, W + 1, w[i])):
			while s < t and a[deq[t - 1]] <= a[cnt]:
				t -= 1
			deq[t] = cnt
			t += 1
			temp[l] = a[deq[s]]
			if cnt - m[i] >= 0:
				if cnt - m[i] == deq[s]:
					s += 1
			temp[l] += cnt * v[i]
	dp = temp
ans = 0
for i in range(1, W + 1):
	ans = max(ans, dp[i])
print(ans)


(N, W) = map(int, input().split())
dp = [0] * (W + 1)
max_weight = 0
for i in range(N):
	(v, w, m) = map(int, input().split())
	n = 1
	while m > 0:
		m -= n
		(_v, _w) = (v * n, w * n)
		max_weight = min(W, max_weight + _w)
		for k in range(max_weight, _w - 1, -1):
			if dp[k] < dp[k - _w] + _v:
				dp[k] = dp[k - _w] + _v
		n = m if n << 1 > m else n << 1
print(max(dp))