You have some number of sticks with positive integer lengths. These lengths are given as an array sticks, where sticks[i] is the length of the ith stick. You can connect any two sticks of lengths x and y into one stick by paying a cost of x + y. You must connect all the sticks until there is only one stick remaining. Return the minimum cost of connecting all the given sticks into one stick in this way.
Input Format
input is managed for you
Output Format
input is managed for you
Constraints
1 <= sticks.length <= 104 1 <= sticks[i] <= 104
Example
Input
3 2 4 3
Output
14