#include<stdio.h>
int pmat(int n, int d[])
{ int c[n+1][n+1], i, j, k, e[n+1][n+1];

  for(i=0;i<=n;i++)
  for(j=0;j<=n;j++) c[i][j]=0;

  for(i=n;i>=0;i--)
  for(j=i+2;j<=n;j++)  
  { int x=~0u>>1, y;
    for(k=i+1;k<j;k++)
    if(y=c[i][k]+c[k][j]+d[i]*d[j]*d[k],y<x)
    x=y, e[i][j]=k;
    c[i][j]=x;
  }

  void aff(int i, int j)
  { if(j==i+1) return;
    int k=e[i][j];
    aff(i,k);
    aff(k,j);
    printf("d[%d]*d[%d]*d[%d]=%d*%d*%d=%d\n",i,k,j,d[i],d[k],d[j],d[i]*d[k]*d[j]); 
  }

  void aff2(int i, int j)
  { if(j==i+1) printf("M%d",j); else
    { int k=e[i][j];
      printf("(");
      aff2(i,k);
      printf("*");
      aff2(k,j);
      printf(")");
    }
  }

  aff2(0,n); printf("\n");
  aff(0,n);
  return c[0][n];
}
int main()
{ int d[]={3,2,4,3,4}, m=pmat(4,d);
  printf("%d\n",m);
  return 0;
}