import sys input = sys.stdin.readline S, N = map(int, input().split()) Weights = [0]*N Values = [0]*N Cnt = [0]*N for i in range(N): Values[i], Weights[i], Cnt[i] = map(int, input().split()) items = [] for i in range(N): w = Weights[i] v = Values[i] c = Cnt[i] k = 1 while c > 0: take = min(k, c) items.append((w * take, v * take)) c -= take k *= 2 dp = [0] * (S+1) for w, v in items: for j in range(S, w-1, -1): dp[j] = max(dp[j], dp[j-w] + v) print(dp[S])

Compiling 'knapsack.py'...

=======
  adding: __main__.pyc (deflated 28%)

=======