Baking Cakes

Tom's birthday is coming up, and you have been put in charge of baking cakes for his enormous birthday party. However, you have a great many cakes to make and very little time, so you are not sure you will even finish before the party!

You are given a list of cakes to make, each requiring a certain amount of time to bake. You have exactly 3 ovens, and each oven can bake only one cake at a time. Assuming that the time required to take one cake out and put another one in is negligible, determine the smallest amount of time you will need to spend baking, given the list of cakes to make.

The input consists of multiple test cases, each on a single line. Each line begins with an integer $n$ (where $1 \le n \le 40$), the number of cakes to bake. It is followed by $n$ integers $t_1, \dots, t_n$ (where $1 \le t_i \le 30$), the time in minutes required to bake each cake. The end of input is marked by a line containing a single $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.