Tug of War

Consider the problem of dividing n children into the fairest teams possible for a game of tug-of-war. The fairest teams are the ones where the collective weights of the children on team 1 are as close as possible to the collective weights of the children on team 2. For this problem, there might be multiple ways to divide the children into fairest teams. Your program may find any optimal division.

Input: balanced.in

The input file (balanced.in) will contain an unknown number of problems. Each problem starts with an integer n (2 ≤ n ≤ 100) that denotes the number of children and an integer k (1 ≤ k ≤ 100) that denotes the weight range of each child (in kilograms). The next n integers contain the weights of the n children in ascending order.

Sample Input File

6 100
13 13 13 13 13 65
3 100
4 5 97

Output: balanced.out

There should be 3 lines of output for each problem in a file named balanced.out. The first line should show the weights of the children on team 1 in ascending order. The second line should show the weights of the children on team 2 in ascending order. The third line should show the weight difference between the two teams. Different problems should be separated by a blank line, although no blank line should follow the final problem.

Timing Constraint: each individual output case should be solved in 2 seconds or less.

Sample Output File

Team 1: 13 13 13 13 13
Team 2: 65
The weight difference is 0

Team 1: 4 5
Team 2: 97
The weight difference is 88