Cut the Legs

A table with four legs may rock, even on a flat surface, if its legs are not all the same length. Interestingly, regardless of how many legs have differing lengths, it is always possible to saw an amount from some legs so as to make the table sit level on a flat surface without rocking. Your job is to generalize this approach to a table with many legs equally spaced around the perimeter of a round table. You are to determine the total length of legs to cut so as to have the table sit level without rocking on a flat surface with not necessarily every leg touching the ground. Input Input consists of data for a number of tables. For each table, a line will give an integer t, between 3 and 50, indicating the number of legs on the table. t subsequent lines will give, in order around the table’s circumference, the lengths of the legs in millimeters. Each leg is perpendicular to the table top. A line containing ‘0’ follows the data for the last table. Output Pick a strategy that cuts the least total length from all legs and print this amount as an integer number. Print a blank line between outputs for each table. Sample Input 3 2000 3000 4000 4 2000 2000 1999 2001 5 2000 2000 1999 2001 1999 0 Sample Output 3000 4 1