1058  Baking Cakes
Time Limit : 5 Second
Memory Limit : 128 MB
Submission: 31
Solved: 7
 Description
 Tom’s birthday is coming up, and you have been put in charge of baking cakes for his monstrous birthday
party. However, you have a great number of cakes to make, and a very short amount of time, so you are not
sure that you will even finish before the party!
You have a list of different cakes to make, each requiring a certain amount of time to bake. You also
have exactly 3 ovens to bake the cakes in, and each oven can only bake one cake at a time. Assuming that
the time required to take a cake out and put another one in is negligible, can you determine the smallest
amount of time you will need to spend baking, given the list of cakes to make?
 Input
 The input test file will contain multiple cases, with each case on a single line. The line begins with an integer
n (where 1 ≤ n ≤ 40), the number of cakes to bake. Following are n integers, t1 , . . . , tn (where 1 ≤ ti ≤ 30),
indicating the time in minutes required to bake each of your cakes. Endofinput is marked by a single line
containing 0; do not process this line.
 Output
 For each test case, output on a single line the smallest amount of time, in minutes, that you need to bake
all of your cakes.
 sample input

1 30 3 15 10 20 5 6 7 8 9 10 0
 sample output

30 20 15
 hint
 source
 Stanford Local 2007