eolymp
bolt
Try our new interface for solving problems
Problems

Sticks

Sticks

Time limit 1 second
Memory limit 128 MiB

The Law of the Jungle says very clearly that every wolf, having acquired a family, can leave his Pack. But as soon as his wolf cubs grow up and get on their feet, he must bring them to the Pack Council, which usually meets once a month, during the full moon, and show them to all the other wolves.

The Father Wolf waited till his cubs grew up and started to run a little. And in one of those nights when flock gathered, he led cubs, Mowgli and Mother Wolf to the Council Rock. It was the top of a hill dotted with large boulders, behind which could hide hundred of wolves. Akela, the great gray lone wolf, who was elected as a leader of the flock for the strength and agility pleaded with his rock:

— You know the law, the law you know! See also, wolves!

Father Wolf pushed into the middle of the circle the Frog Mowgli. Sitting on the ground, Mowgli laughed and began to play with sticks.

He came up with a fairly simple problem — he had to make with these sticks a rectangle of maximum area, to use all the sticks is not necessary.

Input data

The first line contains the number of sticks n~(1 \le n \le 16). The second line contains the lengths of these sticks — the positive integers in the range from 1 to 10^8.

Output data

Print the maximum area of rectangle that can be constructed with this set of sticks, or number 0 if its impossible to construct a rectangle.

Examples

Input example #1
8
7 1 5 2 3 2 4 5 
Output example #1
49
Source 2010 VII Открытый Чемпионат Харькова, I дивизион, 28 ноября, Задача C