Tý có \(N\) ma trận \(A_1, A_2, \dots, A_N\). Ma trận A_i có kích thước \(d_{i-1} \times d_i\). Hãy đặt dấu ngoặc để nhân tất cả các ma trận với tổng phép nhân vô hướng ít nhất. Chi phí nhân ma trận \(p \times q\) và \(q \times r\) là \(p \times q \times r\).

#

Định dạng đầu vào

• Dòng 1: Số nguyên \(N\) (\(1 \le N \le 500\)).
• Dòng 2: \(N+1\) số nguyên \(d_0, d_1, \dots, d_N\) (\(1 \le d_i \le 100\)) mô tả kích thước các ma trận A_i kích thước \(d_{i-1} \times d_i\).

Định dạng đầu ra

• In ra số phép nhân vô hướng tối thiểu để tính tích \(A_1 A_2 \dots A_N\).

Ví dụ

Input:

3
10 100 5 50

Output:

7500

Giải thích: Nhân theo thứ tự \((A_1 A_2) A_3\) tốn \(10 \times 100 \times 5 + 10 \times 5 \times 50 = 5000 + 2500 = 7500\).

Ràng buộc & Subtasks