#n=[10,20,30,7,40,3,61,4,5]
#n=[3,20,4]
#n=[2,100,4,90]
#n=[5,4,6,2,7]
n=[10,100,5,50,1]
s=[[0 for i in range(len(n)-1)] for i in range(len(n)-1)]
def matProd(p):
  global s
  MAX=1000000000
  n=len(p)-1
  m1=[]
  m=[]
  for i in range(n):
    m1=m1+[MAX]
  for i in range(n):
    if (i<n-1):
      m=m+[m1[:i]+[0]+[p[i]*p[i+1]*p[i+2]]+m1[i+2:]]
    else:
      m=m+[m1[:i]+[0]]
  print (m)
  print (s)
  for L in range(2,n):
    for i in range(0,n-L):
      j=i+L
      for k in range(i,j):
        print('i=',i)
        print('k=',k)
        print('j=',j)
        new=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1]
        print(new)
        if (new<m[i][j]):
          m[i][j]=new
          s[i][j]=k
  return m
print(matProd(n)) 
print(s)