You are given an array pieces containing positive integers representing the lengths of wooden pieces.

You can join any two pieces with lengths A and B together, and the cost of joining them is A + B. Repeat this operation until only one piece remains.

Return the least total cost needed to combine all the pieces into one.

Examples

Example 1:
Input: pieces = [3, 5, 2]
Output: 15

Example 2:
Input: pieces = [2, 7, 4, 6]
Output: 35

Constraints

• 2 ≤ pieces.length ≤ 9500
• 1 ≤ pieces[i] ≤ 9500