K. Умножение матриц

Дана цепочка матриц $A_1 \cdot A_2 \cdot \ldots \cdot A_n$, где матрица $A_i$ имеет размер $d_{i-1} \times d_i$. Умножение матриц ассоциативно, но от расстановки скобок зависит количество операций: перемножение матриц $p \times q$ и $q \times r$ стоит $p \cdot q \cdot r$ умножений.

Найдите наименьшее возможное количество умножений.

В первой строке - число $n$ ($1 \le n \le 300$) - количество матриц.

Во второй строке - $n + 1$ число $d_0, d_1, \ldots, d_n$ ($1 \le d_i \le 500$).

Одно число - наименьшее количество умножений.