[Login|Register]
Problems

Status

Rank

Problem 1153
Packing chocolate
Time Limit: 20000ms
Memory Limit: 65536kb
Description
Fuch loves simplicity. For example, he prefer squares better than rectangles.

Fuch has made several square pieces of chocolate, and he's going to pack them into a single square box. All the chocolates must not overlap each other, nor be rotated.

Your task is to write a program to find the smallest box.
Input
Input contains multiple test cases.

The first line of each test case contains a single integer n, indicating the number of chocolates. (1<=n<=8)

The second line contains n positive integers which are no more than 10000, indicating the sizes of each chocolate.

A test case with n=0 indicates the end of input.
Output
For each test case, output the minimum size of box in a single line.

Below figure shows one of the optimal solutions of the last test case.



Sample Input
3
1 2 3
5
1 2 2 2 3
0
Sample Output
5
5
Source
Fuch@USTC
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 0.9ms with 1 query(s).