int dp[501][501];

// cuts[i][j] stores the optimal position to cut the array considering elements i to j
int cuts[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];

	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;
	
}

char name = 'A';
void PrintMCM(int s, int e){
	if(s==e-1){
		cout<<name++;
		return;
	}
	cout<<'(';
	PrintMCM(s, cuts[s][e]);
	PrintMCM(cuts[s][e] + 1, e);
	cout<<')';
}