# TwoSamit-q6
# Sections 31-32, Q.6, p.117, p.268

D = [0,  0,  8, 10, 10, 11, 14, 14, 14, 14, 
    14, 16, 16, 18, 19, 20, 21, 22, 27 ]   
     # added an 0 at start
n = len(D)
K = 9 
S = 107
# q[K][S]
q = [[0 for y in range(S+1)] for x in range(K+1)]
for z in range(S+1):
  q[0][z] = 1
for x in range(1,K+1):
  for z in range(S+1):
    q[x][z] = 0
for x in range(1, n):
  if K < x:
    min = K
  else:
    min = x
  for y in range(min, 0, -1):
    for z in range(S, D[x]-1, -1):
      q[y][z] += q[y-1][z-D[x]]
print("q ==", q[K][S])