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?
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. End-of-input is marked by a single line
containing 0; do not process this line.
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.