You have to cut a piece of wood into n smaller pieces, each piece is of length a_i. The pieces must be cut in order exactly a₁, a₂, ..., a_n from left to right.

At each step, you may cut a piece into two smaller pieces. The cost for that cut is the length of the piece before cut.

Different cut order will result in different costs.

Find the minimum cost to cut the initial piece into n given smaller pieces.