Optimal Merge Cost

You have a list of file sizes. Merging two files of sizes a and b costs a + b, and produces a new file of size a + b.

Return the minimum total cost to merge all files into one.

Function signature

func OptimalMergeCost(sizes []int) int64

Example

sizes = [4,3,2,6]
output = 29

Constraints

• 0 <= len(sizes) <= 200000
• 0 <= sizes[i] <= 1_000_000

Notes

• The optimal strategy always merges the two smallest files first.