คูณเมทริกซ์ 2 (matmul2)

โจทย์

จงเขียนโปรแกรมเพื่อคำนวณว่า เมทริกซ์จำนวน n ตัว มีขนาดต่างๆกัน จะเกิดการคูณสมาชิกในเมทริกซ์น้อยที่สุดกี่ครั้ง ในการคูณลูกโซ่เมทริกซ์

โดยขนาดของเมทริกซ์กำหนดดังนี้ A(i) คือเมทริกซ์ลำดับที่ i จะมีขนาด Dimension(i)*Dimension(i+1) โดย 0<=i<=n-1

ข้อมูลนำเข้า

บรรทัดแรก ประกอบด้วยจำนวนเต็ม n (1<=n<=100) แทนจำนวนเมทริกซ์

บรรทัดถัดมา ประกอบด้วยจำนวนเต็ม n+1 จำนวน แทนขนาดของเมทริกซ์

ข้อมูลส่งออก

บรรทัดเดียว ประกอบด้วยจำนวนเต็ม 1 จำนวน แทนจำนวนการคูณน้อยที่สุดในการคูณลูกโซ่เมทริกซ์นี้

Sample Test Case

input

5
5 10 15 1 10 5

output

275