'''
多重背包模板题
'''from collections import dequearr = []
N, V = map(int, input().split())
for _ in range(N):v, w, s = map(int, input().split())arr.append((v, w, s))dp = [[0] * (V + 1) for _ in range(N)]for i in range(N):# 开销，价值，最大数量ci, wi, si = arr[i]if i == 0:for j in range(V + 1):cnt = min(j // ci, si)dp[i][j] = cnt * wielse:for window_start in range(0, min(V, ci)):dp[i][window_start] = dp[i - 1][window_start]que = deque()que.append((dp[i - 1][window_start], 0)) # [入队数值，入队时间戳]time_cnt = 0for j in range(window_start + ci, V + 1, ci):time_cnt += 1# 删除过期数据while len(que) > 0 and time_cnt - que[0][1] >= si + 1:que.popleft()while len(que) > 0 and que[-1][0] + (time_cnt - que[-1][1]) * wi <= dp[i - 1][j]:que.pop()que.append((dp[i - 1][j], time_cnt))dp[i][j] = que[0][0] + (time_cnt - que[0][1]) * wiprint(dp[N - 1][V])