Polygons on the Grid

The ultimate Tantra is said to have been kept in the most distinguished temple deep in a sacred forest somewhere in Japan. After years of eager research, paleographers finally identified its location: surprisingly, a small temple in Hiyoshi. The temple has an underground secret room built from huge stones, and this megalith is believed to be where the Tantra is enshrined.

The door of the room is, however, securely locked. Legends tell that the key to the lock was an integer known only to the highest priests. As the sect that built the temple declined, that integer became impossible to recover, and the Agency for Cultural Affairs forbids breaking the door open. Fortunately, a figure of a number of rods that may serve as a clue to guess the secret number is engraved on the door.

Many distinguished scholars have challenged the riddle, but none ever succeeded until recently, when a brilliant young computer scientist finally deciphered the puzzle. The lengths of the rods are multiples of a certain unit length. He found that, to find the secret number, all of the rods must be placed on a grid of that unit length to make one convex polygon, and both ends of each rod must be set on grid points. Elementary mathematics tells us that the polygon's area is always an integer multiple of the square of the unit length. The area of the polygon with the largest area is the secret number needed to unlock the door.

For example, if you have five rods whose lengths are 1, 2, 5, 5, and 5, you can make essentially only three kinds of convex polygons, and the maximum area among them is 19.

Your task is to write a program that finds the maximum area of a convex polygon that uses all of the given rods and has both ends of every rod on grid points.

The input consists of multiple datasets, followed by a line containing a single 0 that indicates the end of the input. The format of a dataset is as follows.

n
r1 r2 ... rn

Here n is an integer, the number of rods, and satisfies $3 \le n \le 6$. Each ri is an integer, the length of the i-th rod, and satisfies $1 \le r_i \le 300$.

For each dataset, output a line containing an integer, the area of the largest convex polygon. When there is no possible convex polygon for a dataset, output -1 instead.