GATE Computer Science (CS) 2011 Solved Paper

Four matrices M₁, M₂, M₃ and M₄ of dimensions p × q, q × r, r × s and s × t respectively can be multiplied in several ways with different number of total scalar multiplications. For example when multiplied as ((M₁ ×  M₂) × (M₃ × M₄)), the total number of scalar multiplications is part rst+ prt. When multiplied as ((M1 ×  M2) × (M3 )× M4), the total number of scalar multiplications is pqr+ prs + pst .
If p = 10, g = 100, r = 20, s = 5, and t = 80, then the minimum number of scalar multiplications needed is