from pytokr import item, items

def total(data, choices):
    return sum( data[i] for i in choices )

def powerset(iterable):
    from itertools import chain, combinations # itertools recipe
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def slow_knapsack(weights, values, itq, limw): # copy of the slow reference program
  mx = 0
  best = None
  for cand in powerset(range(itq)):
    if total(weights, cand) <= limw:
      cmx = total(values, cand)
      if cmx > mx:
        best = cand
        mx = cmx
  return best

print("Jutge enters.")

for mxw in items():
    mxw = int(mxw)
    itq = int(item())
    weights = []
    values = []
    for itm in range(itq):
        weights.append(int(item()))
        values.append(int(item()))
    k_ref = slow_knapsack(weights, values, itq, mxw)
    s_ref = sum(values[obj] for obj in k_ref)
    k_test = knapsack(weights, values, itq, mxw)
    s_test = sum(values[obj] for obj in k_test) # Error if objs in k_test out of range
    if s_test != s_ref:
        print("Failure:", s_test, "should be", s_ref)

print("Jutge exits.")
