Given a chain of chain **<M1, M2...Mn>** of **n** two-dimensional matrices, write a program to fully parenthesize the product M1×M2×⋯×Mn in a way that **minimizes** the number of multiplications.

**Problem Note**

**Input:**Array of integers**M**representing a chain of 2-D matrices such that the dimensions of the**ith**matrix is**M[i-1] x M[i]**. Find the most efficient way to multiply these matrices together.**Output:**Return the minimum number of multiplications needed to multiply the chain.- The problem is not actually to perform the multiplications,

but merely to decide in which order to perform the multiplications. - Assume that the matrix dimensions allow multiplication, in order
- Matrix multiplication is associative: M1 (M2M3) = (M1M2) M3

**Example 1**

```
Input: M[] = [40, 20, 30, 10, 30]
Output: 26000
Explanation:
Dimensions of M1 = 40 x 20
Dimensions of M2 = 20 x 30
Dimensions of M3 = 30 x 10
Dimensions of M4 = 10 x 30
First, multiply M2 and M3,cost = 20*30*10 = 6000
Second, multilpy M1 and (Matrix obtained after multilying M2 and M3) = 40 * 20 * 10 = 8000
Third, multiply (Matrix obtained after multiplying M1, M2 and M3) and M4 = 40 * 10 * 30 = 12000
Total Cost = 12000 + 8000 + 6000 =26000
```

**Example 2**

```
Input: A = [10, 20, 30]
Output: 6000
Explanation: There are only two matrices of dimensions 10x20 and 20x30.So there is only one way to multiply the matrices, cost of which is 10*20*30.
```