import sys from collections import deque input = sys.stdin.buffer.readline S, N = map(int, input().split()) dp = [0] * (S+1) for _ in range(N): v, w, c = map(int, input().split()) if c * w >= S: for j in range(w, S+1): dp[j] = max(dp[j], dp[j-w] + v) else: for r in range(w): q = deque() for k in range((S-r)//w + 1): idx = r + k*w val = dp[idx] - k*v while q and q[-1][1] <= val: q.pop() q.append((k, val)) while q and q[0][0] < k - c: q.popleft() dp[idx] = max(dp[idx], q[0][1] + k*v) print(dp[S])

Compiling 'knapsack.py'...

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

=======