Read problems statements in Russian here 
Polo, the Penguin, has a lot of tests tomorrow at the university.
He knows that there are N different questions that will be on the tests. For each question i (i = 1..N), he knows C[i] - the number of tests that will contain this question, P[i] - the number of points that he will get for correctly answering this question on each of tests and T[i] - the amount of time (in minutes) that he needs to spend to learn this question.
Unfortunately, the amount of free time that Polo has is limited to W minutes. Help him to find the maximal possible total number of points he can get for all tests if he studies for no more than W minutes.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains the pair of integers N and W, separated by a space. The following N lines contain three space-separated integers C[i], P[i] and T[i] (i = 1..N).

------ Output ------ 

For each test case, output a single line containing the answer to the corresponding test case.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 100$
$1 ≤ C[i], P[i], T[i] ≤ 100
$$1 ≤ W ≤ 100$

----- Sample Input 1 ------ 
1
3 7
1 2 3
2 3 5
3 3 3
----- Sample Output 1 ------ 
11
----- explanation 1 ------ 
Example case 1. The best choice is to learn the first and the third questions and get 1*2 + 3*3 = 11 points.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Dynamic programming


Solutions:
def maximal_points(T, tests):
	for t in range(T):
		(N, W) = map(int, input().split())
		(C, P, T) = ([], [], [])
		for i in range(N):
			(c, p, t) = map(int, input().split())
			C.append(c)
			P.append(p)
			T.append(t)
		dp = [[0 for j in range(W + 1)] for i in range(N + 1)]
		for i in range(1, N + 1):
			for j in range(1, W + 1):
				if j < T[i - 1]:
					dp[i][j] = dp[i - 1][j]
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - T[i - 1]] + C[i - 1] * P[i - 1])
		print(dp[N][W])
T = int(input())
tests = [0] * T
maximal_points(T, tests)


import sys
from collections import deque
import math

def maxPoints(i, arr, time, n, dp):
	if time == 0 or i == n:
		return 0
	if dp[i][time] == -1:
		q = arr[i]
		l = 0
		if time >= q[2]:
			l = q[0] * q[1] + maxPoints(i + 1, arr, time - q[2], n, dp)
		r = maxPoints(i + 1, arr, time, n, dp)
		dp[i][time] = max(l, r)
	return dp[i][time]
t = int(input())
for i in range(t):
	(n, w) = map(int, input().split())
	arr = []
	for i in range(n):
		inp = list(map(int, input().split()))
		arr.append(inp)
	dp = [[-1] * 101 for _ in range(n)]
	print(maxPoints(0, arr, w, n, dp))


for _ in range(int(input())):
	(N, W) = map(int, input().split())
	l = []
	for i in range(N):
		(c, p, t) = map(int, input().split())
		l.append((c, p, t))
	dp = [0] * (W + 1)
	for i in range(N):
		cur = l[i]
		for j in range(W, -1, -1):
			if j - cur[2] >= 0:
				dp[j] = max(dp[j], dp[j - cur[2]] + cur[0] * cur[1])
	print(dp[W])


from collections import defaultdict
number_of_testcases = int(input())
for _ in range(number_of_testcases):
	options = defaultdict(int)
	options[0] = 0
	best_option_points = 0
	(n, w) = map(int, input().split(' '))
	for _ in range(n):
		(num_tests, points, time) = map(int, input().split(' '))
		for (option_time, option_points) in options.copy().items():
			new_time = option_time + time
			new_points = option_points + num_tests * points
			if option_time + time <= w:
				if new_points > options[new_time]:
					options[new_time] = new_points
					if best_option_points < new_points:
						best_option_points = new_points
	print(best_option_points)


for _ in range(int(input())):
	(N, W) = map(int, input().split())
	V = [[0 for j in range(W + 1)] for k in range(N + 1)]
	C = [0 for i in range(N + 1)]
	P = [0 for i in range(N + 1)]
	T = [0 for i in range(N + 1)]
	for i in range(1, N + 1):
		(C[i], P[i], T[i]) = map(int, input().split())
	for m in range(N + 1):
		for n in range(W + 1):
			if m == 0 or n == 0:
				V[m][n] == 0
			elif T[m] > n:
				V[m][n] = V[m - 1][n]
			else:
				V[m][n] = max(V[m - 1][n], V[m - 1][n - T[m]] + C[m] * P[m])
	print(V[m][n])


for _ in range(int(input())):
	(n, w) = map(int, input().split())
	arr = [[0 for j in range(w + 1)] for i in range(n + 1)]
	cp = []
	tn = []
	for i in range(n):
		(c, p, t) = map(int, input().split())
		cp.append(c * p)
		tn.append(t)
	for i in range(n + 1):
		for j in range(w + 1):
			if i == 0 or j == 0:
				arr[i][j] = 0
			elif tn[i - 1] <= j:
				arr[i][j] = max(arr[i - 1][j], cp[i - 1] + arr[i - 1][j - tn[i - 1]])
			else:
				arr[i][j] = arr[i - 1][j]
	print(arr[n][w])


def solve():
	lis = list()
	(n, w) = map(int, input().split())
	for i in range(n):
		lis.append(list(map(int, input().split())))
	dp = [[0] * (w + 1) for i in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(w + 1):
			if j >= lis[i - 1][2]:
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - lis[i - 1][2]] + lis[i - 1][1] * lis[i - 1][0])
			else:
				dp[i][j] = dp[i - 1][j]
	print(dp[n][w])
for _ in range(int(input())):
	solve()


def knapSack(W, wt, val, n):
	dp = [0 for i in range(W + 1)]
	for i in range(1, n + 1):
		for w in range(W, 0, -1):
			if wt[i - 1] <= w:
				dp[w] = max(dp[w], dp[w - wt[i - 1]] + val[i - 1])
	return dp[W]

def soln(n, W, c, p, t):
	res = 0
	val = [c[i] * p[i] for i in range(n)]
	dp = [0 for i in range(W + 1)]
	for i in range(1, n + 1):
		for w in range(W, 0, -1):
			if t[i - 1] <= w:
				dp[w] = max(dp[w], dp[w - t[i - 1]] + val[i - 1])
	return dp[W]
for _ in range(int(input())):
	(n, w) = map(int, input().split())
	c = []
	p = []
	t = []
	for i in range(n):
		(x, y, z) = map(int, input().split())
		c.append(x)
		p.append(y)
		t.append(z)
	print(soln(n, w, c, p, t))


def knapSack(W, wt, val, n):
	K = [[0 for x in range(W + 1)] for x in range(n + 1)]
	for i in range(n + 1):
		for w in range(W + 1):
			if i == 0 or w == 0:
				K[i][w] = 0
			elif wt[i - 1] <= w:
				K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])
			else:
				K[i][w] = K[i - 1][w]
	return K[n][W]
for _ in range(int(input())):
	(n, w) = [int(x) for x in input().split(' ')]
	v = []
	t = []
	for i in range(n):
		(a, b, c) = [int(x) for x in input().split(' ')]
		v.append(a * b)
		t.append(c)
	print(knapSack(w, t, v, n))


def knapsack(wt, val):
	K = [[0 for x in range(W + 1)] for x in range(n + 1)]
	for i in range(n + 1):
		for w in range(W + 1):
			if i == 0 or w == 0:
				K[i][w] = 0
			elif T[i - 1] <= w:
				K[i][w] = max(C[i - 1] * P[i - 1] + K[i - 1][w - T[i - 1]], K[i - 1][w])
			else:
				K[i][w] = K[i - 1][w]
	return K[n][W]
t = int(input())
for _ in range(t):
	(n, W) = list(map(int, input().split()))
	C = [-1 for _ in range(n)]
	P = [-1 for _ in range(n)]
	T = [-1 for _ in range(n)]
	for i in range(n):
		(C[i], P[i], T[i]) = list(map(int, input().split()))
	print(knapsack(0, 0))


T = int(input())
for t in range(T):
	(N, W) = map(int, input().split())
	C = [0 for i in range(N)]
	P = [0 for i in range(N)]
	T = [0 for i in range(N)]
	for n in range(N):
		(C[n], P[n], T[n]) = map(int, input().split())
	dp = [[0 for j in range(W + 1)] for i in range(N + 1)]
	for i in range(1, N + 1):
		for j in range(W + 1):
			if j >= T[i - 1]:
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - T[i - 1]] + C[i - 1] * P[i - 1])
			else:
				dp[i][j] = dp[i - 1][j]
	print(dp[N][W])


from functools import lru_cache

def max_points(questions, time):

	@lru_cache(maxsize=None)
	def mx(qi, time):
		if time < 0:
			return -10 ** 8
		if time == 0:
			return 0
		if qi == -1:
			return 0
		return max(mx(qi - 1, time - questions[qi][1]) + questions[qi][0], mx(qi - 1, time))
	return mx(len(questions) - 1, time)
for _ in range(int(input())):
	(n, time) = [int(x) for x in input().split()]
	questions = []
	for _ in range(n):
		(a, b, c) = [int(x) for x in input().split()]
		questions.append((a * b, c))
	print(max_points(questions, time))


for _ in range(int(input())):
	(n, w) = list(map(int, input().split()))
	questions = []
	for _ in range(n):
		(c, p, t) = list(map(int, input().split()))
		questions.append((c * p, t))
	dp = [[0] * (w + 1) for _ in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, w + 1):
			case1 = dp[i - 1][j]
			case2 = 0
			if j >= questions[i - 1][1]:
				case2 = dp[i - 1][j - questions[i - 1][1]] + questions[i - 1][0]
			dp[i][j] = max(case1, case2)
	print(dp[n][w])


t = int(input())
for _ in range(t):
	(n, w) = [int(x) for x in input().split()]
	cp = [0 for i in range(n)]
	t = [0 for i in range(n)]
	for i in range(n):
		(c, p, t[i]) = [int(x) for x in input().split()]
		cp[i] = c * p
	dp = [[0 for j in range(w + 1)] for i in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, w + 1):
			dp[i][j] = dp[i - 1][j]
			if j - t[i - 1] >= 0:
				dp[i][j] = max(dp[i][j], cp[i - 1] + dp[i - 1][j - t[i - 1]])
	print(dp[n][w])


t = int(input())
for _ in range(t):
	(n, w) = map(int, input().split())
	items = []
	for _ in range(n):
		(c, p, t) = map(int, input().split())
		items.append((c * p, t))
	dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, w + 1):
			if j < items[i - 1][1]:
				dp[i][j] = dp[i - 1][j]
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - items[i - 1][1]] + items[i - 1][0])
	print(dp[n][w])


for _ in range(int(input())):
	(n, W) = map(int, input().split())
	p = []
	q = []
	for i in range(n):
		l = list(map(int, input().split()))
		p.append(l[0] * l[1])
		q.append(l[2])
	dp = [0 for i in range(W + 1)]
	for i in range(1, n + 1):
		for w in range(W, 0, -1):
			if w >= q[i - 1]:
				dp[w] = max(dp[w], dp[w - q[i - 1]] + p[i - 1])
	print(dp[W])


for _ in range(int(input())):
	(n, w) = list(map(int, input().split()))
	a = [0] + [-1] * w
	for i in range(n):
		(c, p, t) = map(int, input().split())
		for j in range(w, t - 1, -1):
			if a[j - t] >= 0:
				a[j] = max(a[j], a[j - t] + c * p)
	print(max(a))


for _ in range(int(input())):
	(n, w) = map(int, input().split())
	k = []
	for i in range(n):
		a = [int(i) for i in input().split()]
		k.append([a[0] * a[1], a[2]])
	knap = [[0 for i in range(w + 1)] for j in range(n + 1)]
	for i in range(n + 1):
		for j in range(w + 1):
			if i == 0 or j == 0:
				knap[i][j] = 0
			elif k[i - 1][1] <= j:
				knap[i][j] = max(k[i - 1][0] + knap[i - 1][j - k[i - 1][1]], knap[i - 1][j])
			else:
				knap[i][j] = knap[i - 1][j]
	print(knap[n][w])


def knapsack(l1, l2, W, n):
	dp = [0 for i in range(W + 1)]
	for i in range(n):
		for w in range(W, 0, -1):
			if l2[i] <= w:
				dp[w] = max(dp[w], dp[w - l2[i]] + l1[i])
	return dp[W]
t = int(input())
for i in range(t):
	(n, w) = map(int, input().split())
	l1 = []
	l2 = []
	for j in range(n):
		(c, p, t) = map(int, input().split())
		l1 += [c * p]
		l2 += [t]
	ans = knapsack(l1, l2, w, n)
	print(ans)


import numpy as np
t = int(input())
for _ in range(t):
	(n, w) = map(int, input().split())
	C = []
	P = []
	T = []
	for _ in range(n):
		(c, p, t) = map(int, input().split())
		C.append(c)
		P.append(p)
		T.append(t)
	S = np.zeros((n + 1, w + 1), int)
	for i in range(1, n + 1):
		time = T[i - 1]
		total_score = P[i - 1] * C[i - 1]
		for a in range(w + 1):
			if a < time:
				S[i][a] = S[i - 1][a]
			else:
				S[i][a] = max(S[i - 1][a], S[i - 1][a - time] + total_score)
	print(S[n][w])


t = int(input())

def knapsack(tim_i, value, w, n):
	if n == 0 or w == 0:
		return 0
	elif tim_i[n - 1] <= w:
		if dp[n - 1][w - tim_i[n - 1]] == -1:
			dp[n - 1][w - tim_i[n - 1]] = knapsack(tim_i, value, w - tim_i[n - 1], n - 1)
			if dp[n - 1][w] == -1:
				dp[n - 1][w] = knapsack(tim_i, value, w, n - 1)
		elif dp[n - 1][w] == -1:
			dp[n - 1][w] = knapsack(tim_i, value, w, n - 1)
		return max(value[n - 1] + dp[n - 1][w - tim_i[n - 1]], dp[n - 1][w])
	else:
		if dp[n - 1][w] == -1:
			dp[n - 1][w] = knapsack(tim_i, value, w, n - 1)
		return dp[n - 1][w]
for _ in range(t):
	(n, w) = map(int, input().split())
	time_i = []
	val = []
	for i in range(n):
		(c, p, tim) = map(int, input().split())
		time_i.append(tim)
		val.append(c * p)
	dp = [[-1 for i in range(w + 1)] for j in range(n + 1)]
	ans = knapsack(time_i, val, w, n)
	print(ans)


def knapsack(w, t, pt, n):
	knap = [[0 for i in range(w + 1)] for j in range(n + 1)]
	for i in range(n + 1):
		for j in range(w + 1):
			if i == 0 or j == 0:
				knap[i][j] = 0
			elif t[i - 1] <= j:
				knap[i][j] = max(pt[i - 1] + knap[i - 1][j - t[i - 1]], knap[i - 1][j])
			else:
				knap[i][j] = knap[i - 1][j]
	print(knap[n][w])
for _ in range(int(input())):
	(n, w) = map(int, input().split())
	c = []
	p = []
	t = []
	for i in range(n):
		val = input().split()
		c.append(int(val[0]))
		p.append(int(val[1]))
		t.append(int(val[2]))
	pt = [c[i] * p[i] for i in range(n)]
	knapsack(w, t, pt, n)


def solve(n, w, dp, s, t):
	if n == 0 or w == 0:
		return 0
	if dp[n - 1][w] != -1:
		return dp[n - 1][w]
	if w >= t[n - 1]:
		dp[n - 1][w] = max(s[n - 1] + solve(n - 1, w - t[n - 1], dp, s, t), solve(n - 1, w, dp, s, t))
		return dp[n - 1][w]
	else:
		dp[n - 1][w] = solve(n - 1, w, dp, s, t)
		return dp[n - 1][w]
	return dp[n - 1][w]
for _ in range(int(input())):
	(n, w) = map(int, input().split())
	C = []
	T = []
	for i in range(n):
		(c, p, t) = map(int, input().split())
		C.append(c * p)
		T.append(t)
	dp = [[-1 for j in range(w + 1)] for i in range(n + 1)]
	print(solve(n, w, dp, C, T))


t = int(input())
for _ in range(t):
	(m, w) = [int(x) for x in input().split()]
	score = []
	weight = []
	for line in range(m):
		(a, b, c) = [int(x) for x in input().split()]
		score.append(a * b)
		weight.append(c)
	n = len(score)
	t = [[-1 for i in range(w + 1)] for j in range(n + 1)]

	def knapsack(wt, val, W, n):
		if n == 0 or W == 0:
			return 0
		if t[n][W] != -1:
			return t[n][W]
		if wt[n - 1] <= W:
			t[n][W] = max(val[n - 1] + knapsack(wt, val, W - wt[n - 1], n - 1), knapsack(wt, val, W, n - 1))
			return t[n][W]
		elif wt[n - 1] > W:
			t[n][W] = knapsack(wt, val, W, n - 1)
			return t[n][W]
	print(knapsack(weight, score, w, n))


for _ in range(int(input())):
	(n, W) = list(map(int, input().split()))
	c = [-1 for _ in range(n)]
	p = [-1 for _ in range(n)]
	t = [-1 for _ in range(n)]
	for i in range(n):
		(c[i], p[i], t[i]) = list(map(int, input().split()))
	dp = [[0 for i in range(W + 1)] for i in range(n + 1)]
	for i in range(1, n + 1):
		for w in range(1, W + 1):
			if t[i - 1] <= w:
				dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - t[i - 1]] + c[i - 1] * p[i - 1])
			else:
				dp[i][w] = dp[i - 1][w]
	print(dp[n][W])


t = int(input())
for test in range(t):
	(n, w) = list(map(int, input().split()))
	time = []
	points = []
	for i in range(n):
		(a, b, c) = list(map(int, input().split()))
		time.append(c)
		points.append(a * b)
	dp = [0 for i in range(w + 1)]
	for i in range(1, n + 1):
		temp = [0 for k in range(w + 1)]
		for j in range(1, w + 1):
			if time[i - 1] <= j:
				temp[j] = max(dp[j - time[i - 1]] + points[i - 1], dp[j])
			else:
				temp[j] = dp[j]
		dp = temp[:]
	print(dp[w])


mod = 1000000007
read_int = lambda : int(input().strip())
read_str = lambda : input().strip()
read_str_arr = lambda : input().strip().split()
read_int_arr = lambda : [int(x) for x in input().strip().split()]

def solve():
	(n, w) = read_int_arr()
	c = [0] * n
	p = [0] * n
	t = [0] * n
	for i in range(n):
		(c[i], p[i], t[i]) = read_int_arr()
	kp = [[0] * (w + 1) for _ in range(2)]
	for i in range(n):
		for j in range(1, w + 1):
			if j >= t[i]:
				kp[1][j] = max(kp[0][j], c[i] * p[i] + kp[0][j - t[i]])
			else:
				kp[1][j] = kp[0][j]
		for j in range(1, w + 1):
			kp[0][j] = kp[1][j]
	print(kp[0][-1])
for _ in range(int(input())):
	solve()


T = int(input())
for _ in range(T):
	(N, W) = map(int, input().split())
	C = []
	P = []
	T = []
	for i in range(N):
		(a, b, c) = map(int, input().split())
		C.append(a)
		P.append(b)
		T.append(c)
	val = []
	for i in range(N):
		val.append(C[i] * P[i])
	dp = [[0] * (W + 1) for i in range(N + 1)]
	for i in range(1, N + 1):
		for j in range(1, W + 1):
			if T[i - 1] <= j:
				dp[i][j] = max(val[i - 1] + dp[i - 1][j - T[i - 1]], dp[i - 1][j])
			else:
				dp[i][j] = dp[i - 1][j]
	print(dp[-1][-1])


def solve(n, val, wt, W):
	K = [[0 for x in range(W + 1)] for x in range(n + 1)]
	for i in range(n + 1):
		for w in range(W + 1):
			if i == 0 or w == 0:
				K[i][w] = 0
			elif wt[i - 1] <= w:
				K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])
			else:
				K[i][w] = K[i - 1][w]
	return K[n][W]
for _ in range(int(input())):
	(n, w) = map(int, input().split())
	C = []
	T = []
	for i in range(n):
		(c, p, t) = map(int, input().split())
		C.append(c * p)
		T.append(t)
	print(solve(n, C, T, w))


t = int(input())
for _ in range(t):
	(n, w) = map(int, input().split())
	time_i = []
	val = []
	for i in range(n):
		(c, p, tim) = map(int, input().split())
		time_i.append(tim)
		val.append(c * p)
	dp = [[-1 for j in range(w + 1)] for i in range(n + 1)]
	for i in range(n + 1):
		for j in range(w + 1):
			if i == 0 or j == 0:
				dp[i][j] = 0
	for i in range(1, n + 1):
		for j in range(1, w + 1):
			if time_i[i - 1] <= j:
				dp[i][j] = max(val[i - 1] + dp[i - 1][j - time_i[i - 1]], dp[i - 1][j])
			else:
				dp[i][j] = dp[i - 1][j]
	print(dp[n][w])


def knapSack(W, wt, val, n):
	K = [[0 for x in range(W + 1)] for x in range(n + 1)]
	for i in range(n + 1):
		for w in range(W + 1):
			if i == 0 or w == 0:
				K[i][w] = 0
			elif wt[i - 1] <= w:
				K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])
			else:
				K[i][w] = K[i - 1][w]
	return K[n][W]
t = int(input())
for _ in range(t):
	(n, w) = map(int, input().split())
	score = []
	time = []
	for _ in range(n):
		(ci, pi, ti) = map(int, input().split())
		score.append(ci * pi)
		time.append(ti)
	print(knapSack(w, time, score, n))


from itertools import combinations
for tc in range(int(input())):
	(a, b) = map(int, input().split())
	x = []
	c = []
	p = []
	t = []
	for i in range(a):
		(q, w, e) = map(int, input().split())
		c.append(q)
		p.append(w)
		t.append(e)
	for i in range(a):
		x.append(p[i] * c[i])
	s = [[0] * (b + 1) for i in range(a + 1)]
	for i in range(1, a + 1):
		for j in range(1, b + 1):
			if t[i - 1] <= j:
				s[i][j] = max(x[i - 1] + s[i - 1][j - t[i - 1]], s[i - 1][j])
			else:
				s[i][j] = s[i - 1][j]
	print(s[-1][-1])


def solve_test_case():
	(n, w) = map(int, input().split())
	dp = [[0] * (w + 1) for _ in range(n + 1)]
	for i in range(1, n + 1):
		(c, p, t) = map(int, input().split())
		for j in range(1, w + 1):
			dp[i][j] = dp[i - 1][j]
			if j >= t and dp[i - 1][j - t] + c * p > dp[i][j]:
				dp[i][j] = dp[i - 1][j - t] + c * p
	return dp[n][w]
t = int(input())
for _ in range(t):
	print(solve_test_case())


for _ in range(int(input())):
	(n, W) = map(int, input().split())
	data = [[0, 0, 0, 0, 0] for _ in range(n)]
	m = [[0] * (W + 1) for _ in range(n + 1)]
	for i in range(n):
		(data[i][0], data[i][1], data[i][2]) = map(int, input().split())
		data[i][3] = data[i][0] * data[i][1]
		data[i][4] = data[i][3] / data[i][2]
	for k in range(1, n + 1):
		for w in range(W + 1):
			if data[k - 1][2] > w:
				m[k][w] = m[k - 1][w]
			else:
				m[k][w] = max(m[k - 1][w], m[k - 1][w - data[k - 1][2]] + data[k - 1][3])
	i = 0
	ans = m[n][w]
	print(int(ans))


for _ in range(int(input())):
	(n, w) = map(int, input().split())
	ans = []
	for i in range(n + 1):
		ans.append([0] * (w + 1))
	for i in range(n):
		(c, p, t) = map(int, input().split())
		value = c * p
		for j in range(w):
			if j + 1 < t:
				ans[i + 1][j + 1] = ans[i][j + 1]
			else:
				ans[i + 1][j + 1] = max(ans[i][j + 1], value + ans[i][j + 1 - t])
	print(int(ans[n][w]))


def maxpoint(time, points, i, w, memo):
	key = (i, w)
	if key in memo:
		return memo[key]
	if w <= 0:
		return 0
	if i >= len(time):
		return 0
	take = 0
	if w - time[i] >= 0:
		take = points[i] + maxpoint(time, points, i + 1, w - time[i], memo)
	nottake = maxpoint(time, points, i + 1, w, memo)
	memo[key] = max(take, nottake)
	return memo[key]
case = int(input())
for _ in range(case):
	(n, w) = map(int, input().split(' '))
	points = []
	time = []
	for i in range(n):
		(c, p, t) = map(int, input().split(' '))
		points.append(c * p)
		time.append(t)
	memo = {}
	res = maxpoint(time, points, 0, w, memo)
	print(res)


t = int(input())
for i in range(t):
	(N, W) = map(int, input().split())
	knapsack_table = [[0 for i in range(W + 1)] for k in range(N + 1)]
	for j in range(N + 1):
		if j == 0:
			continue
		(C, P, T) = [int(n) for n in input().split()]
		for k in range(W + 1):
			if T <= k:
				knapsack_table[j][k] = max(knapsack_table[j - 1][k], knapsack_table[j - 1][k - T] + C * P)
			else:
				knapsack_table[j][k] = knapsack_table[j - 1][k]
	print(knapsack_table[N][W])


def mx_pnt(W, tm, pnt, n):
	M = [[0 for i in range(W + 1)] for j in range(n + 1)]
	for i in range(n + 1):
		for j in range(W + 1):
			if i == 0 or j == 0:
				M[i][j] = 0
			elif tm[i - 1] <= j:
				M[i][j] = max(pnt[i - 1] + M[i - 1][j - tm[i - 1]], M[i - 1][j])
			else:
				M[i][j] = M[i - 1][j]
	return M[i][W]
for _ in range(int(input())):
	(n, W) = map(int, input().split())
	c = []
	p = []
	t = []
	for i in range(n):
		(c1, p1, t1) = list(map(int, input().split()))
		c.append(c1)
		p.append(p1)
		t.append(t1)
	v = [c[i] * p[i] for i in range(n)]
	ans = mx_pnt(W, t, v, n)
	print(ans)


NBCASE = int(input())
for ncase in range(NBCASE):
	s = input()
	T = []
	Val = []
	(N, W) = map(int, s.split(' '))
	for i in range(N):
		s = input()
		(c, p, t) = map(int, s.split(' '))
		T.append(t)
		Val.append(c * p)
	DP = [[0 for j in range(1 + W)] for i in range(1 + N)]
	for i in range(1, N + 1):
		for j in range(1, W + 1):
			if T[i - 1] > j:
				DP[i][j] = DP[i - 1][j]
			else:
				DP[i][j] = max(Val[i - 1] + DP[i - 1][j - T[i - 1]], DP[i - 1][j])
	print(DP[N][W])


def solve(n, w, val, wt, dp):
	if w == 0 or n == 0:
		return 0
	if dp[n][w] != -1:
		return dp[n][w]
	if wt[n - 1] <= w:
		dp[n][w] = max(val[n - 1] + solve(n - 1, w - wt[n - 1], val, wt, dp), solve(n - 1, w, val, wt, dp))
		return dp[n][w]
	else:
		dp[n][w] = solve(n - 1, w, val, wt, dp)
		return dp[n][w]
t = int(input())
while t:
	(N, W) = map(int, input().split())
	marks = []
	time = []
	dp = []
	for i in range(N + 1):
		dp.append([-1] * (W + 1))
	for i in range(N):
		(ci, pi, ti) = map(int, input().split())
		marks.append(ci * pi)
		time.append(ti)
	print(solve(N, W, marks, time, dp))
	t -= 1


import numpy as np
import random

def polodp(times, points, total_time, total_ques):
	l = [[0 for _ in range(total_time + 1)] for _ in range(total_ques + 1)]
	for idx1 in range(total_ques + 1):
		for idx2 in range(total_time + 1):
			if idx1 == 0 or idx2 == 0:
				l[idx1][idx2] = 0
			elif times[idx1 - 1] <= idx2:
				l[idx1][idx2] = max(points[idx1 - 1] + l[idx1 - 1][idx2 - times[idx1 - 1]], l[idx1 - 1][idx2])
			else:
				l[idx1][idx2] = l[idx1 - 1][idx2]
	return l[-1][-1]
for i in range(int(input())):
	(n, total_time) = map(int, input().split())
	(times, points) = ([], [])
	for _ in range(n):
		(c, p, t) = map(int, input().split())
		times.append(t)
		points.append(c * p)
	print(polodp(times, points, total_time, n))


import math
import random
import statistics
from collections import Counter
import heapq
import operator
import itertools
import sys
import functools
import bisect
import copy
for _ in range(int(input())):
	(KPN, KPW) = [int(x) for x in input().split()]
	KPD = [0] * (KPW + 1)
	for i in range(KPN):
		(KPC, KPP, KPT) = [int(x) for x in input().split()]
		for j in range(KPW, KPT - 1, -1):
			KPD[j] = max(KPD[j - KPT] + KPC * KPP, KPD[j])
	print(KPD[-1])


for _ in range(int(input())):
	(n, w) = map(int, input().split())
	cost = []
	weight = []
	for i in range(n):
		(c, p, t) = map(int, input().split())
		cost.append(c * p)
		weight.append(t)
	l = [[-1 for i in range(w + 1)] for j in range(len(weight) + 1)]
	for i in range(len(weight) + 1):
		l[i][0] = 0
	for i in range(1, len(weight) + 1):
		for j in range(1, w + 1):
			if weight[i - 1] <= j:
				if l[i - 1][j - weight[i - 1]] != -1 and l[i - 1][j] != -1:
					l[i][j] = max(l[i - 1][j], l[i - 1][j - weight[i - 1]] + cost[i - 1])
				if l[i - 1][j - weight[i - 1]] == -1 and l[i - 1][j] != -1:
					l[i][j] = l[i - 1][j]
				if l[i - 1][j - weight[i - 1]] != -1 and l[i - 1][j] == -1:
					l[i][j] = l[i - 1][j - weight[i - 1]] + cost[i - 1]
			elif l[i - 1][j] != -1:
				l[i][j] = l[i - 1][j]
	print(max(*l[-1]))


for _ in range(int(input())):
	(n, w) = map(int, input().split())
	l = []
	for i in range(n):
		(c, p, t) = map(int, input().split())
		l.append([t, c * p])
	l.sort()
	score = []
	time = []
	for i in l:
		time.append(i[0])
		score.append(i[1])
	m = [[0 for x in range(w + 1)] for y in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, w + 1):
			if j < time[i - 1]:
				m[i][j] = m[i - 1][j]
			else:
				m[i][j] = max(m[i - 1][j], m[i - 1][j - time[i - 1]] + score[i - 1])
	print(m[-1][-1])


def knapsack(n, val, T, W):
	K = [[0 for x in range(W + 1)] for y in range(2)]
	for i in range(n + 1):
		for w in range(W + 1):
			if i == 0 or w == 0:
				K[i % 2][w] = 0
			elif T[i - 1] <= w:
				K[i % 2][w] = max(val[i - 1] + K[(i - 1) % 2][w - T[i - 1]], K[(i - 1) % 2][w])
			else:
				K[i % 2][w] = K[(i - 1) % 2][w]
	return K[n % 2][W]
t = int(input())
while t > 0:
	(n, w) = map(int, input().split())
	qList = [list(map(int, input().split())) for i in range(n)]
	Q = []
	T = []
	for i in range(n):
		v = int(qList[i][0]) * int(qList[i][1])
		Q.append(v)
		T.append(int(qList[i][2]))
	points = knapsack(n, Q, T, w)
	print(points)
	t -= 1


import math
testcase = int(input())
dp = [-math.inf] * 105
for T in range(testcase):
	(n, w) = map(int, input().split())
	for i in range(1, w + 1):
		dp[i] = -math.inf
	dp[0] = 0
	for i in range(n):
		(c, p, t) = map(int, input().split())
		for j in range(w, t - 1, -1):
			if dp[j - t] >= 0:
				dp[j] = max(dp[j], dp[j - t] + p * c)
	ans = 0
	for i in range(1, w + 1):
		ans = max(ans, dp[i])
	print(ans)


for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	points = []
	time = []
	for i in range(n):
		temp = [int(i) for i in input().split()]
		points.append(temp[0] * temp[1])
		time.append(temp[2])
	dp = [[0 for i in range(k + 1)] for j in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, k + 1):
			if time[i - 1] > j:
				dp[i][j] = dp[i - 1][j]
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - time[i - 1]] + points[i - 1])
	print(dp[n][k])


def max_points(N, W, C, P, T):
	dp = [[0] * (W + 1) for _ in range(N + 1)]
	for i in range(1, N + 1):
		for j in range(1, W + 1):
			case1 = dp[i - 1][j]
			case2 = 0
			if j >= T[i - 1]:
				case2 = dp[i - 1][j - T[i - 1]] + C[i - 1] * P[i - 1]
			dp[i][j] = max(case1, case2)
	return dp[N][W]
T = int(input())
for _ in range(T):
	(N, W) = map(int, input().split())
	C = []
	P = []
	T = []
	for _ in range(N):
		(c, p, t) = map(int, input().split())
		C.append(c)
		P.append(p)
		T.append(t)
	result = max_points(N, W, C, P, T)
	print(result)


t = int(input())
for i in range(t):
	st = input().split()
	N = int(st[0])
	W = int(st[1])
	SC = [0 for x in range(W + 1)]
	for k in range(N):
		st = input().split()
		C = int(st[0])
		P = int(st[1])
		T = int(st[2])
		p = W
		m = C * P
		while p >= T:
			s = SC[p - T] + m
			if s > SC[p]:
				SC[p] = s
			p -= 1
	print(SC[W])


t = int(input())
for x in range(t):
	T = [int(a) for a in input().split()]
	n = T[0]
	w = T[1]
	info = []
	c = 0
	for y in range(n):
		i = [int(a) for a in input().split()]
		mv = i[0] * i[1]
		i.insert(0, mv)
		info.append(i)
	h = [[0 for a in range(w + 1)] for b in range(n)]
	for i in range(n):
		for j in range(w + 1):
			if i == 0:
				if j >= info[0][3]:
					h[0][j] = info[0][0]
			elif j >= info[i][3]:
				h[i][j] = max(info[i][0] + h[i - 1][j - info[i][3]], h[i - 1][j])
			else:
				h[i][j] = h[i - 1][j]
	print(h[n - 1][w])


T = int(input())
for _ in range(T):
	(N, W) = map(int, input().split())
	CPT = [tuple(map(int, input().split())) for _ in range(N)]
	dp = [[0] * (W + 1) for _ in range(N + 1)]
	for i in range(1, N + 1):
		(c, p, t) = CPT[i - 1]
		for j in range(W + 1):
			if j >= t:
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - t] + c * p)
			else:
				dp[i][j] = dp[i - 1][j]
	print(dp[N][W])


for t in range(int(input())):
	(n, w) = map(int, input().split())
	lt = []
	for i in range(n):
		(c, p, t) = map(int, input().split())
		lt.append([c, p, t])
	dp = []
	for i in range(n + 1):
		dp.append([0] * (w + 1))
	for i in range(1, n + 1):
		for j in range(1, w + 1):
			if lt[i - 1][2] > j:
				dp[i][j] = dp[i - 1][j]
			else:
				x = j - lt[i - 1][2]
				dp[i][j] = max(dp[i - 1][j], lt[i - 1][0] * lt[i - 1][1] + dp[i - 1][x])
	print(dp[-1][-1])


for _ in range(int(input())):
	(N, W) = list(map(int, input().split()))
	dp = [0] * (W + 1)
	for i in range(N):
		(c, p, t) = list(map(int, input().split()))
		cp = c * p
		for j in range(W, t - 1, -1):
			dp[j] = max(dp[j], dp[j - t] + cp)
	print(dp[-1])


for _ in range(int(input())):
	(n, p) = map(int, input().split())
	d = [0 for x in range(p + 1)]
	for l in range(n):
		(a, b, c) = map(int, input().split())
		m = a * b
		k = p
		while k >= c:
			s = d[k - c] + m
			if s > d[k]:
				d[k] = s
			k = k - 1
	print(d[p])


def knapsack(n, item, cost, size):
	dp = [[None for i in range(size + 1)] for j in range(n + 1)]
	for x in range(size + 1):
		for y in range(n + 1):
			if x == 0:
				dp[y][0] = 0
				continue
			if y == 0:
				dp[0][x] = 0
				continue
			if cost[y - 1] > x:
				dp[y][x] = dp[y - 1][x]
			else:
				dp[y][x] = max(dp[y - 1][x - cost[y - 1]] + item[y - 1], dp[y - 1][x])
	return dp[n][size]
t = int(input())
while t > 0:
	(n, w) = map(int, input().split())
	qList = [list(map(int, input().split())) for i in range(n)]
	Q = []
	T = []
	for i in range(n):
		v = int(qList[i][0]) * int(qList[i][1])
		Q.append(v)
		T.append(int(qList[i][2]))
	points = knapsack(n, Q, T, w)
	print(points)
	t -= 1


def knapsack(l, t, n, w):
	dp = [[0 for j in range(w + 1)] for i in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, w + 1):
			if t[i - 1] <= j:
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - t[i - 1]] + l[i - 1])
			else:
				dp[i][j] = dp[i - 1][j]
	return dp[n][w]
for _ in range(int(input())):
	(n, w) = map(int, input().split())
	(c, p, t) = ([], [], [])
	for i in range(n):
		(x, y, z) = map(int, input().split())
		c.append(x)
		p.append(y)
		t.append(z)
	l = []
	for i in range(n):
		l.append(c[i] * p[i])
	print(knapsack(l, t, n, w))


def knapSack(W, wt, val, n):
	dp = [0 for i in range(W + 1)]
	for i in range(1, n + 1):
		for w in range(W, 0, -1):
			if wt[i - 1] <= w:
				dp[w] = max(dp[w], dp[w - wt[i - 1]] + val[i - 1])
	return dp[W]
for _ in range(int(input())):
	(n, limit) = list(map(int, input().split()))
	arr = [0] * n
	for i in range(n):
		arr[i] = list(map(int, input().split()))
		arr[i] = (arr[i][0] * arr[i][1], arr[i][2])
	Values = [arr[i][0] for i in range(n)]
	Weights = [arr[i][1] for i in range(n)]
	print(knapSack(limit, Weights, Values, n))


def knapSack(W, wt, val, n):
	dp = [0 for i in range(W + 1)]
	for i in range(1, n + 1):
		for w in range(W, 0, -1):
			if wt[i - 1] <= w:
				dp[w] = max(dp[w], dp[w - wt[i - 1]] + val[i - 1])
	return dp[W]
t = int(input())
for i in range(t):
	[N, W] = [int(i) for i in input().split()]
	val = []
	weight = []
	for i in range(N):
		lst = [int(i) for i in input().split()]
		val.append(lst[0] * lst[1])
		weight.append(lst[2])
	print(knapSack(W, weight, val, N))


T = int(input())
for i in range(T):
	(N, W) = map(int, input().split())
	dp = [0] * (W + 1)
	for j in range(N):
		(c_j, p_j, t_j) = map(int, input().split())
		for k in range(W, t_j - 1, -1):
			dp[k] = max(dp[k - t_j] + c_j * p_j, dp[k])
	print(dp[-1])


for _ in range(int(input())):
	(N, W) = map(int, input().split())
	SC = [0 for x in range(W + 1)]
	for i in range(N):
		(C, P, T) = map(int, input().split())
		p_ = W
		m = C * P
		while p_ >= T:
			s = SC[p_ - T] + m
			if s > SC[p_]:
				SC[p_] = s
			p_ -= 1
	print(SC[W])