행렬 곱셈 순서 4

크기가 $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 2$인 경우에 행렬의 곱 $ABC$를 구하는 경우를 생각해보자.

• $AB$를 먼저 곱하고 $C$를 곱하는 경우, $(AB)C$에 필요한 곱셈 연산의 수는 $5 \times 3 \times 2 + 5 \times 2 \times 2 = 30 + 20 = 50$번이다.
• $BC$를 먼저 곱하고 $A$를 곱하는 경우, $A(BC)$에 필요한 곱셈 연산의 수는 $3 \times 2 \times 2 + 5 \times 3 \times 2 = 12 + 30 = 42$번이다.

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

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

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

둘째 줄부터 $N+1$번째 줄까지, $i+1$번째 줄에는 $i$번째 행렬의 크기 $r_i$과 $c_i$가 주어진다. ($1 \le r_i, c_i \le 10{,}000$)

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

주어지는 행렬의 크기는 단조감소함이 보장된다. 즉, $1 \le i < j \le n$에 대해 $r_i \ge r_j$이고 $c_i \ge c_j$이다.

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