cs_103 Ghép các đống sỏi

Có N đống sỏi xếp thành một hàng, đống thứ i có A_i viên sỏi. Ta có thể ghép hai đống sỏi kề nhau thành một đống và mất một chi phí bằng tổng hai đống sỏi đó. Hãy tìm cách ghép N đống sỏi này thành một đống với chi phí là nhỏ nhất.

Ví dụ, có 5 đống sỏi: 4 1 2 7 5

Ta có thể ghép 1 với 2, 4 với 3, 7 với 5 và 5 với 12

Chi phí = 3 + 7 + 12 + 19 = 41

Dữ liệu vào có dạng:

• Dòng đầu là số N (N<101) là số đống sỏi. • Dòng thứ 2 gồm N số nguyên là số sỏi của N đống sỏi. (0<A_i<1001)</p>

Dữ liệu ra: một số nguyên là chi phí nhỏ nhất

INPUT1

5

4 1 2 7 5

OUTPUT1

41