행렬 곱셈 순서 2

크기가 $N \times M$인 행렬 $A$와 크기가 $M \times K$인 행렬 $B$를 곱하려면 $N \times M \times K$번의 곱셈이 필요하다. $N$개의 행렬을 곱하는 데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라진다.

예를 들어 $A$의 크기가 $5 \times 3$, $B$의 크기가 $3 \times 2$, $C$의 크기가 $2 \times 6$인 경우에 행렬의 곱 $ABC$를 구하는 경우를 생각해 보자.

• $AB$를 먼저 곱하고 $C$를 곱하면 $(AB)C$에 필요한 곱셈 연산의 수는 $5 \times 3 \times 2 + 5 \times 2 \times 6 = 30 + 60 = 90$번이다.
• $BC$를 먼저 곱하고 $A$를 곱하면 $A(BC)$에 필요한 곱셈 연산의 수는 $3 \times 2 \times 6 + 5 \times 3 \times 6 = 36 + 90 = 126$번이다.

같은 곱셈이라도 순서에 따라 곱셈 연산의 수가 달라진다.

행렬 $N$개의 크기가 주어졌을 때, 모든 행렬을 곱하는 데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다.

첫째 줄에 행렬의 개수 $N$($1 \le N \le 20{,}000$)이 주어진다.

둘째 줄부터 $N$개 줄에는 행렬의 크기 $r$과 $c$가 주어진다. ($1 \le r, c \le 10{,}000$)

입력으로는 순서대로 곱셈을 할 수 있는 크기만 주어진다.

첫째 줄에 입력으로 주어진 행렬을 곱하는 데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 $2^{63}-1$보다 작거나 같은 자연수이다. 최악의 순서로 연산해도 연산 횟수는 $2^{63}-1$보다 작거나 같다.