2169. Baking Cakes

单点时限: 2.0 sec

内存限制: 256 MB

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.

样例

Input
1 30
3 15 10 20
5 6 7 8 9 10
0
Output
30
20
15

11 人解决,26 人已尝试。

23 份提交通过,共有 136 份提交。

7.1 EMB 奖励。

创建: 13 年,11 月前.

修改: 4 年前.

最后提交: 4 月前.

来源: Stanford Local 2007

题目标签