행렬 곱셈 순서

크기가 $N \times M$인 행렬 $A$와 크기가 $M \times K$인 행렬 $B$를 곱할 때 필요한 곱셈 연산은 모두 $N \times M \times K$번이다. 행렬 여러 개를 곱할 때 필요한 곱셈 연산의 수는 곱하는 순서에 따라 달라진다.

$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 500$)

둘째 줄부터 $N$개 줄에 행렬의 크기 $r$과 $c$가 곱하는 순서대로 한 줄에 하나씩 주어진다. ($1 \le r, c \le 500$)

주어진 순서 그대로 곱셈을 할 수 있는 크기만 입력으로 주어진다. 즉, $i$번째 행렬의 열 개수는 $i+1$번째 행렬의 행 개수와 같다.

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