Cho ~N~ đoạn thẳng có độ dài nguyên. Biết rằng có thể ghép các đoạn thẳng này thành một đa giác lồi trên mặt phẳng tọa độ Descartes sao cho các đỉnh của đa giác đều có tọa độ nguyên và diện tích của đa giác cũng là một số nguyên.

Yêu cầu: Hãy xác định diện tích lớn nhất của một đa giác có thể tạo được từ các đoạn thẳng đã cho.

Ví dụ, với ~N=5~ và độ dài các đoạn thẳng là ~1,2,5,5,5~, có thể tạo được ba đa giác thỏa mãn. Diện tích lớn nhất thu được là ~19~.

Input

• Dòng đầu tiên chứa số nguyên ~N~ ~(3 \le N \le 6)~;

• Dòng thứ hai chứa ~N~ số nguyên là độ dài của các đoạn thẳng, mỗi độ dài thuộc đoạn ~[1,300]~.

Output

Một số nguyên duy nhất là diện tích lớn nhất của đa giác có thể tạo được.

Sample Input 1

5
1 2 5 5 5

Sample Output 1

19