SP3927 MPOLGRID - Polygon on the Grid

传说中，终极密教经典被珍藏在日本一座隐秘的圣林深处著名的寺庙中。经过多年热切的研究，古文字学家终于确定了它的位置，令人意外的是，它竟在日吉的一座小寺庙里。这座寺庙拥有一个用巨石建造的地下密室，据说经典就安放在其中。 然而，密室的门被牢牢锁住了。传说中，门锁的钥匙是一个整数，只有高阶神职人员才知晓。随时间推移，建造寺庙的宗派逐渐衰落，这个整数已无人知晓。而文化厅也禁止破坏门锁。幸运的是，门上刻有棍子的图案，可能为推测该秘密数字提供线索。 很多学者挑战过这一谜题，但无一成功，直到最近，一位才华横溢的年轻计算机科学家成功解开了谜团。这些棍子的长度均为某个单位长度的倍数。他��现，找到这个秘密数字的方法是：将所有棍子放置在一个单位长度的网格上，形成一个凸多边形，且每根棍子的两端必须位于网格点上。基础数学告诉我们，这个多边形的面积应是单位长度平方的整数倍。最终，面积最大的那个多边形面积就是用于解锁密室门的秘密数字。 例如，假设你有五根长度分别为1，2，5，5和5的棍子，你可以构造出如图1所示的三种不同的多边形，最大面积为19。  你的任务是编写一个程序，利用所有给定的棍子在网格点上寻找能够形成的最大凸多边形的面积。

输入由多个数据集组成，每个数据集后接一行仅包含一个零，表示输入结束。数据集格式如下： n r1 r2 … rn 其中，$n$为整数，表示棍子的数量，满足 $3 \le n \le 6$。$r_i$为第$i$根棍子的长度，满足 $1 \le r_i \le 300$。

对于每个数据集，输出一个整数，表示能形成的最大凸多边形面积。如果无法构造任何凸多边形，则输出“-1”。 **本翻译由 AI 自动生成**