#include <stdio.h>
#include <stdlib.h>

#define MAX 2000
#define INF 0x7FFF


int A[MAX+1][MAX+1];

int max(int a, int b)
{
    if (a > b) return(a);
    else return(b);
}

int main()
{
    int D[7], N = 6;
    int p, k, i, j, best, temp;
    char c;

    D[0]=30; D[1]=35; D[2]=15; D[3]=5; D[4]=10; D[5]=20; D[6]=25;
    for (i = 1; i <= N; i++)
        A[i][i] = 0;
        
    for (p = 2; p <= N; p++) {
        printf("p = %d:\n", p);
        for (i = 1; i <= N-p+1; i++) {
            j = i+p-1; best = INF;
            for (k = i; k <= j-1; k++) {
                temp = A[i][k] + A[k+1][j] + D[i-1]*D[k]*D[j];
                printf("\tM[A%d..A%d] = %5d: M[A%d..A%d] (%5d) + M[A%d..A%d] (%5d) + %5d\n",
                            i, j, temp, i, k, A[i][k], k+1, j, A[k+1][j], D[i-1]*D[k]*D[j]);
                if (best > temp) best = temp;
            }
            A[i][j] = best; printf("\n"); 
        }
        scanf("%c\n", &c);
    }
}