# Task
John is an orchard worker. 

There are `n` piles of fruits waiting to be transported. Each pile of fruit has a corresponding weight. John's job is to combine the fruits into a pile and wait for the truck to take them away.

Every time, John can combine any two piles(`may be adjacent piles, or not`), and the energy he costs is equal to the weight of the two piles of fruit.

For example, if there are two piles, pile1's weight is `1` and pile2's weight is `2`. After merging, the new pile's weight is `3`, and he consumed 3 units of energy.

John wants to combine all the fruits into 1 pile with the least energy.

Your task is to help John, calculate the minimum energy he costs.

# Input

- `fruits`: An array of positive integers. Each element represents the weight of a pile of fruit.
  
  Javascript:
  - 1 <= fruits.length <= 10000
  - 1 <= fruits[i] <= 10000
  
  Python:
  - 1 <= len(fruits) <= 5000
  - 1 <= fruits[i] <= 10000

# Output

An integer. the minimum energy John costs.


# Examples

For `fruits = [1,2,9]`, the output should be `15`.

```
3 piles:  1  2  9
combine 1 and 2 to 3, cost 3 units of energy.
2 piles:  3  9
combine 3 and 9 to 12, cost 12 units of energy.
1 pile:  12

The total units of energy is 3 + 12 = 15 units
```

For `fruits = [100]`, the output should be `0`.

There's only 1 pile. So no need combine it.

Difficulty: introductory

Starter code:

def comb(fruits):
	

Solutions:
from heapq import heappop, heappush

def comb(fruits):
    total, heap = 0, sorted(fruits)
    while len(heap) > 1:
        cost = heappop(heap) + heappop(heap)
        heappush(heap, cost)
        total += cost
    return total

import bisect
from collections import deque
def comb(fruits):
    energy = 0
    fruits = deque(sorted(fruits))
    while len(fruits) > 1:
        e = fruits.popleft() + fruits.popleft()
        energy +=  e
        bisect.insort_left(fruits, e)
    return energy

from heapq import heapify, heappop, heappush

def comb(fruits):
    ws = list(fruits)
    heapify(ws)
    res = 0
    while len(ws) > 1:
        w = heappop(ws) + heappop(ws)
        heappush(ws, w)
        res += w
    return res

from heapq import heappop, heappush


def comb(fruits):
    total, fruits = 0, sorted(fruits)
    for _ in range(len(fruits) - 1):
        energy = heappop(fruits) + heappop(fruits)
        heappush(fruits, energy)
        total += energy
    return total

from heapq import heapify, heappush, heappop

def comb(fruits):
    energy = 0
    heapify(fruits)
    while len(fruits) > 1:
        cost = heappop(fruits) + heappop(fruits)
        heappush(fruits, cost)
        energy += cost
    return energy

from bisect import insort

def comb(fruits):
    fruits = sorted(fruits)
    total_cost = 0
    while len(fruits) > 1:
        cost = sum(fruits[:2])
        total_cost += cost
        del fruits[:2]
        insort(fruits, cost)
    return total_cost

from heapq import heapify, heappop, heapreplace

def comb(fruits):
    fruits = fruits[:]
    heapify(fruits)
    total_cost = 0
    for i in range(len(fruits) - 1):
        cost = heappop(fruits)
        cost += fruits[0]
        total_cost += cost
        heapreplace(fruits, cost)
    return total_cost

from heapq import heapify, heappop, heappush


def comb(fruits):
    heapify(fruits)
      
    energy_total = 0
    while len(fruits) > 1:
        energy_used = heappop(fruits) + heappop(fruits)
        heappush(fruits, energy_used)
        energy_total += energy_used
    
    return energy_total


import heapq

def comb(fruits):
    heapq.heapify(fruits)
    w = 0
    while len(fruits) > 1:
        x, y = heapq.heappop(fruits), heapq.heappop(fruits)
        w += x + y
        heapq.heappush(fruits, x + y)
    return w


def bin_insert(n, lst):
    start = 0
    end = len(lst) - 1

    while start < end:
        check = (start + end) // 2

        if lst[check] == n:
            return check
        
        if lst[check] < n:
            start = check + 1
        else:
            end = check - 1

    if len(lst) != 0 and lst[start] < n:
        return start + 1
    return start

def comb(fruits):
    fruits.sort()
    res = 0
    while len(fruits) > 1:
        wt = fruits.pop(0) + fruits.pop(0)
        res += wt
        fruits.insert(bin_insert(wt, fruits), wt)
    return res