# 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
#
# O(NC) time and space solution

def ks_tab(v,w,C):
  N = len(v)
  tab = [ [ 0 for c in range(C+1) ] for n in range(N+1) ]
  n,c = 1,0
  while n!=N+1:
    if c==C+1: n,c = n+1,0
    else:
      tab[n][c] = tab[n-1][c]
      if w[n-1]<=c:
        tab[n][c] = max(tab[n][c],v[n-1]+tab[n-1][c-w[n-1]])
      c += 1
  return tab[N][C]