int dp[501][501];

int MCM(int s, int e, int v[]){
    
    if(s==e-1) return 0;
    else if(dp[s][e]!=-1) return dp[s][e];
    
	/*
		   [ 0   1   2   3   4   5 ]
       v = [ a   b   c   d   e   f ]
       cuts =    1   2   3   4
	   
	   Recurrence Relation : 
	   Min cost of multiplying (S, E) at cut k = Min cost of multiplying(S, k) + Min cost of multiplying(k, E) + V[S]*V[K]*V[E]
	   ( As the resultant matrices will be of dim V[S]*V[k] and  V[k]*V[E] and cost to multiply i*j with j*k is i*j*k )
	*/
	
    int ans = INT_MAX;
    for(int k=s+1;k<=e-1;k++)
        ans = min(ans, MCM(s, k, v) + MCM(k, e, v) + v[s]*v[k]*v[e] );
    
    return dp[s][e] = ans;
    
}

int matrixMultiplication(int N, int v[])
{
	int dp[501][501] = {0};

	for(int s=N-1;s>=0;s--){
		for(int e=s+2;e<N;e++){
			dp[s][e] = INT_MAX;
			for(int k=s+1;k<=e-1;k++)
				dp[s][e] = min( dp[s][e], dp[s][k] + dp[k][e] + v[s]*v[k]*v[e] );
		}
	}

	return dp[0][N-1];
}