code: def heaviest_increasing_subsequence(a, debug=False):
      
      # Stores the smallest idx of last element of a subsequence of weight w
      L = {0: -1}
      bestsofar = [(0, -1)] * len(a)  # (best weight, from_idx)
      for i, (key, weight) in enumerate(a):
  
          for w, j in L.items():
              if j != -1 and a[j][0] >= key:
                  continue
  
              new_weight = w + weight
              if new_weight in L and a[L[new_weight]][0] <= key:
                  continue
  
              L[new_weight] = i
              newbest = (new_weight, j)
              if newbest > bestsofar[i]:
                  bestsofar[i] = newbest
  
          if debug:
              #print (key, weight), L
              print((key, weight), bestsofar)
  
      tb = reversed(list(backtracking(a, L, bestsofar)))
      return [a[x] for x in tb], max(L.items())[0]
docs: Returns the heaviest increasing subsequence for array a. Elements are (key,
      weight) pairs.
  
      >>> heaviest_increasing_subsequence([(3, 3), (2, 2), (1, 1), (0, 5)])
      ([(0, 5)], 5)