## Story

There are four warriors, they need to go through a dark tunnel. Tunnel is very narrow, every time only can let two warriors through, and there are lot of dangerous traps. Fortunately, they have a lamp that can illuminate the tunnel to avoid being trapped by the trap.

In order to pass this tunnel, they need five steps:

1. Two people go through the tunnel with the lamp
2. And then one people come back with the lamp
3. And then two people go through the tunnel with the lamp
4. And then one people come back with the lamp
5. And then two people go through the tunnel with the lamp
 
Each warrior has his own walking speed, we need to calculate the shortest time they have to cross the tunnel.
 
For example:
 
Four warriors is `a,b,c,d`. Their speed are `[3,4,5,6]`. It means they need 3 minutes, 4 minutes, 5 minutes and 6 minutes to cross the tunnel. The shortest crossing time should be 21 minutes, the method is as follows:
 
```
a and b go through the tunnel  ---> Spend 4 minutes
(Time spent should be calculated by the person who is slow)
a come back                    ---> Spend 3 minutes
a and c go through the tunnel  ---> Spend 5 minutes
a come back                    ---> Spend 3 minutes
a and d go through the tunnel  ---> Spend 6 minutes
```
Do you have any other better way?
 
## Task
Complete function `shortestTime()` that accepts 1 argument: `speed` that are the spent time of four warriors. Returns the shortest time that all warriors go through the tunnel.
 
**Note: The method in example above is not always the best way.**

## Example

Difficulty: EASY
Tags: Game theory

Ad-hoc

Starter code:
def shortest_time(speed):
	

Solutions:
def shortest_time(speed):
	(a, b, c, d) = sorted(speed)
	return a + b + d + min(2 * b, a + c)


from itertools import combinations

def shortest_time(xs, ys=[]):
	if len(xs) == 2:
		return max(xs)
	result = 999999999
	for (i, j) in combinations(range(len(xs)), 2):
		m = max(xs[i], xs[j])
		xs2 = xs[:i] + xs[i + 1:j] + xs[j + 1:]
		ys2 = ys + [xs[i], xs[j]]
		for (k, y) in enumerate(ys2):
			result = min(m + y + shortest_time(xs2 + [y], ys2[:k] + ys2[k + 1:]), result)
	return result


shortest_time = lambda a: a.sort() or a[0] + a[1] + min(2 * a[1], a[0] + a[2]) + a[3]


def shortest_time(speed):
	import itertools
	from collections import Counter
	times = []
	for elem in itertools.combinations(speed, 2):
		end1 = [x for x in elem]
		base1 = list((Counter(speed) - Counter(end1)).elements())
		for i in itertools.combinations(end1, 1):
			base2 = [x for x in base1 + [i[0]]]
			if sum(end1) != 2 * end1[0]:
				end2 = [x for x in end1 if x != i[0]]
			else:
				end2 = [end1[0]]
			for j in itertools.combinations(base2, 2):
				end3 = [x for x in end2 + [j[0], j[1]]]
				base3 = list((Counter(base2) - Counter(j)).elements())
				for k in itertools.combinations(end3, 1):
					base4 = [x for x in base3 + [k[0]]]
					times += [max(elem) + i[0] + max(j) + k[0] + max(base4)]
	return min(times)


from math import inf
from itertools import chain, combinations, combinations_with_replacement

def shortest_time(speed: [int]):
	forward_trips_num = 3
	best_time = inf
	for forward_trips in combinations_with_replacement(list(combinations(speed, 2)), forward_trips_num):
		if any((list(chain(*forward_trips)).count(s) < speed.count(s) for s in set(speed))):
			continue
		sum_forward = sum([max(trip[0], trip[1]) for trip in forward_trips])
		sum_return = 0
		returns = {s: 0 for s in set(speed)}
		for s in set(speed):
			returns[s] += sum([trip.count(s) for trip in forward_trips]) - speed.count(s)
			sum_return += returns[s] * s
		if best_time > sum_forward + sum_return:
			best_time = sum_forward + sum_return
	return best_time


def shortest_time(speed):
	speed.sort()
	[a, b, c, d] = speed
	return min(a + 3 * b + d, 2 * a + b + c + d)


def shortest_time(speed):
	speed.sort()
	return speed[0] + speed[1] + speed[3] + min(2 * speed[1], speed[0] + speed[2])


def shortest_time(speed):
	speed.sort()
	o = 3 * speed[1] + speed[0] + speed[3]
	t = sum(speed[1:]) + (len(speed) - 2) * speed[0]
	return o if o <= t else t


def shortest_time(speed):
	copy = speed
	copy.sort()
	y = copy[0] + copy[1] * 3 + copy[3]
	minimum = copy.pop(0)
	answers = list()
	x = sum(copy) + minimum * (len(copy) - 1)
	answers.append(x)
	answers.append(y)
	return min(answers)


def shortest_time(speed):
	speed = sorted(speed)
	return min(speed[1] * 3 + speed[0] + speed[3], speed[0] + sum(speed))