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()) dp = [[0]*(S+1) for _ in range(N+1)] dp[0][0] = 0 for i in range(1, N+1): w = Weights[i-1] v = Values[i-1] c = Cnt[i-1] for j in range(S+1): Weights[i][j] = Weights[i-1][j] for j in range(S, w-1, -1): for k in range( c+1): if j - k*w < 0: break dp[i][j] = max(dp[i][j], dp[i-1][j - k*w] + k*v) print(dp[N][S])

Compiling 'knapsack.py'...

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

=======