Balanced Teams

Interview

Time limit1sMemory limit128 MB

Summary

Split twelve cows with given skill levels into four teams of three to minimize the gap between the strongest and weakest team sums.

Level: Medium4 of 10
Topics: Brute force, Backtracking
Solved: No attempts yet

Problem

Twelve of Farmer John's cows are competing in this year's winter Moolympics. Each cow has a skill level that is an integer between 1 and 1,000,000.

Farmer John wants to split them into four teams of three. The skill level of a team is the sum of the skill levels of its three cows. He wants the four teams to be as evenly matched as possible, so he wants to minimize $S - s$ , where $S$ is the largest team skill level and $s$ is the smallest.

Write a program that finds the smallest possible value of $S - s$ .

Input

Each of the twelve lines contains the skill level of one cow. Every skill level is an integer between 1 and 1,000,000.

Output

Print the smallest possible value of $S - s$ on the first line.

Hint

Suppose the skill levels are 1 through 12, one per line. Splitting the cows into (12, 1, 7), (9, 8, 3), (10, 5, 4), (11, 2, 6) gives the first two teams a skill level of 20 and the other two a skill level of 19. Here $S - s$ is 1, and no split does better.

Examples1

Example 1
Input
```
1
2
3
4
5
6
7
8
9
10
11
12
```
Expected output
```
1
```