# input: v[0..N) and w[0..N) arrays of natural numbers, N>=0, and C>=0
#
# output: Maximum retribution by choosing elements with individual
#         retribution and weight in v[0..N) and w[0..N), respectively,
#         to carry in a knapsack with weight capacity C
#
# exponential (in N ans C) naive solution

def ks_naive(v,w,C):
  return ks_aux(v,w,len(v),C)

def ks_aux(v,w,n,c):
  ans = None
  if n==0: ans = 0
  else:
    ans = ks_aux(v,w,n-1,c)
    if w[n-1]<=c:
      ans = max(ans,v[n-1]+ks_aux(v,w,n-1,c-w[n-1]))
  return ans