#149행렬을 곱하는 최적의 순서

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

예를 들어, A의 크기가 5×3, B의 크기가 3×2, C의 크기가 2×6일 때 행렬의 곱 ABC를 구하는 경우를 생각해 보자.

AB를 먼저 곱하고 C를 곱하는 (AB)C는 5×3×2 + 5×2×6 = 30 + 60 = 90번의 곱셈 연산이 필요하다.
BC를 먼저 곱하고 A를 곱하는 A(BC)는 3×2×6 + 5×3×6 = 36 + 90 = 126번의 곱셈 연산이 필요하다.

같은 곱셈이지만 곱하는 순서에 따라 곱셈 연산의 수가 달라진다.

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

첫째 줄에 행렬의 개수 N(1 ≤ N ≤ 500)이 주어진다.

둘째 줄부터 N개 줄에 걸쳐 행렬의 크기 r과 c가 주어진다. (1 ≤ r, c ≤ 500)

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

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