Challenge: Join the Ropes

Lab Java Intermediate 20 points

You have ropes of different lengths. Joining two ropes of lengths a and b costs a + b and makes one rope of that length. Join all ropes into one with the smallest total cost. Trick: always join the two shortest ropes.

Input

Line 1: n (n ≥ 1). Line 2: n rope lengths.

Output

The minimum total cost.

Example

Input

4
4 3 2 6

Output

Sample input available Sample output available

Editor

Java

Hints

Put all lengths in a min-heap.

Repeat: poll the two shortest, add their sum to the cost, offer the sum back.

Solution explanation

Short ropes get joined early, and long ones late, so big lengths are added as few times as possible. n − 1 joins, each O(log n): O(n log n). Use long – costs grow fast.

Show solution

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        PriorityQueue<Long> pq = new PriorityQueue<Long>();
        for (int i = 0; i < n; i++) pq.offer(sc.nextLong());
        long cost = 0;
        while (pq.size() > 1) {
            long a = pq.poll(), b = pq.poll();
            cost += a + b;
            pq.offer(a + b);
        }
        System.out.println(cost);
    }
}

Output

Answer