// problem #98

행렬 곱셈 순서

여러 행렬을 곱할 때 곱셈 연산 횟수가 최소가 되도록 괄호를 묶는 경우의 연산 횟수를 구하시오.

입력

첫 줄 행렬 개수 N. 이후 N개 줄에 각 행렬의 행 크기와 열 크기.

출력

최소 곱셈 연산 횟수.

제한

• 1 ≤ N ≤ 500
• 행렬 크기 ≤ 500

예제

3
5 3
3 2
2 6

90

2
50 10
10 40

20000