import sys input = sys.stdin.readline S, N = map(int, input().split()) by_weight = {} for _ in range(N): v, w, k = map(int, input().split()) if w <= S and k > 0: if w not in by_weight: by_weight[w] = [] by_weight[w].append((v, k)) weights_sorted = sorted(by_weight.keys()) best = [[-10**18] * (S + 1) for _ in range(len(weights_sorted) + 1)] best[0][0] = 0 idx = 1 for w in weights_sorted: items = by_weight[w] items.sort(reverse=True) for curW in range(0, S + 1): best[idx][curW] = best[idx - 1][curW] copies = 0 type_idx = 0 used = 0 profit = 0 while (copies + 1) * w <= curW and type_idx < len(items): copies += 1 profit += items[type_idx][0] prev = best[idx - 1][curW - copies * w] if prev > -10**18: best[idx][curW] = max(best[idx][curW], prev + profit) used += 1 if used == items[type_idx][1]: used = 0 type_idx += 1 idx += 1 print(max(best[len(weights_sorted)]))

Compiling 'knapsack.py'...

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

=======