Description

Bear is the instructor's housemate's pet dog. Being an awesome husky, Bear sort of does whatever she wants [1]. For instance, she just loves chilling out on top of the air conditioning vents in the house; they keep her cool and relaxed. Fortunately for Bear, there are vents in every room of the house, all lined up against the wall as so:

|| [vent]   [vent]    [vent] ||

Since huskies tend to be active and energetic dogs, Bear often gets restless and moves from one vent to another. Paradoxically, she also displays some laziness, and hates moving too much once she is in her relaxed state. Moreover, after moving to one vent, Bear always returns to her original one.

Your job is to figure out the optimal vent for each room that minimizes the total distance from that optimal vent to all the others.

Once you have figured out this information, Bear will know which vent to start at in each room, thus keeping herself cool and relaxed and not having to expend too much energy.

Input

Each line in the input represents a room. The first string is the name of the room, which is followed by the number of vents in the room (no more than 10) and then the distances of the vents from wall. Note, that since the vents are lined up against the wall, these can be considered linear distances. Likewise, some rooms may have multiple vents at the same location.

Sample input:

Living 2 4 2
Ryan's 3 2 4 7

Output

For each room, output the name of the room, the location of the optimal vent, and the minimal sum of distances from the optimal vent to each of the other vents. Distances between two vents v_i and v_j is d_ij = | v_i - v_j |. In the case of multiple optimal vents, select the one closest to the wall (smallest v_i).

Sample output:

Living 2 2
Ryan's 4 5

[1]	Obey Ryan's dog.

Approach

The optimal vent is the median of the vents, so simply sort the vents according to distance from the left wall, select the median vent and then compute the total distances from the median to all the other vents.

Input/Output

• Final Input: problem009.input
• Final Output: problem009.output

Source Code

• Peter Bui's source code: pbui.c
• Dominic Golab's source code: dgolab.cpp
• Raymond Le Grand's source code: rlegrand.cc