일렬로 나열된 K개의 숫자가 주어집니다. 이 숫자들을 다음 규칙에 따라 최종적으로 하나의 덩어리로 합치려고 합니다.

1. 한 번에 서로 인접한 두 개의 덩어리만 하나로 합칠 수 있습니다.
2. 두 덩어리를 하나로 합칠 때마다 (두 덩어리의 숫자 합)만큼의 비용이 누적됩니다.

최종적으로 하나의 덩어리가 될 때까지 발생하는 총 누적 비용의 최솟값을 구하는 프로그램을 작성하시오.

합치는 순서에 따라 총 비용이 달라집니다.

입력

첫째 줄에 숫자의 개수 K가 주어진다. 둘째 줄에는 K개의 숫자가 공백으로 구분되어 순서대로 주어진다.

출력

모든 숫자를 하나로 합치는 데 필요한 최소 누적 비용을 첫째 줄에 출력한다.

제한 사항

• 3 ≤ K ≤ 500
• 각 숫자는 10,000 이하의 자연수이다.

예제 입력 1

4
40 30 30 50

예제 출력 1

300

예제 설명 1

[40, 30, 30, 50] 이 있을 때,

• 가운데 [30, 30]을 먼저 합치면 합인 60이 비용으로 쌓이고, 수열은 [40, 60, 50]이 됩니다. (누적 비용: 60)
• 그 다음 [40, 60]을 합치면 합인 100이 비용으로 쌓이고, 수열은 [100, 50]이 됩니다. (누적 비용: 60 + 100 = 160)
• 마지막으로 [100, 50]을 합치면 합인 150이 비용으로 쌓이고 하나의 덩어리가 됩니다. (최종 누적 비용: 160 + 150 = 310)

하지만 다른 순서로 합쳐서 [40, 30]을 먼저 합치고(비용 70), [30, 50]을 합친 뒤(비용 80), 마지막 두 덩어리를 합치면 70 + 80 + 150 = 300이 되어 이 경우가 최소 비용이 됩니다.