拼合残梭

意识迷宫的第四层，是一片由断裂金属构成的森林。地上散落着无数根断裂的穿梭机残骸——有些长，有些短，每一根都刻着旧时代的编号。它们曾属于同一支舰队，如今却碎成了零件。

"要把它们拼成若干组推进器。"Echo说，"每组的残骸总长度必须完全相同。组数越多越好——这意味着能复原的推进器越多。"

CC捡起一根最长的残片，掂了掂："先拼长的还是先拼短的？"

"先拼长的。"你说，"长的残片选择少——能放进哪个组基本是定的。如果先拼短的，可能后面发现长的那根无处可放，整盘都得推翻重来。"

"这和拼图一样嘛。"CC想了想，"先放边角，再放中间。"

"对。"你说，"而且如果发现某一组已经超长了，立刻停止往里面加。如果一根残片放不进任何一组，而且它的长度刚好等于目标总长，那它自己就可以成为新的一组。如果总和根本不能被组数整除，那从一开始就是不可能的。"

你蹲下来，把残片按长度从大到小排开。最长的那根像一把断剑，你把它放进第一组的底座。然后是第二长的、第三长的……每次放入前都仔细丈量，生怕哪一组突然超重。有一次，你差点把两根等长的残片放进同一组，CC在旁边咳嗽了一声，你猛地停住，撤回其中一根，换了一条更短的补上。

当第四十七号残片——最长的一根——被稳稳放进第一组时，所有组同时发出低沉的共鸣。

"又是四十七。"CC说。

"最长的一根。"Echo说，"Zero把自己比作那根最长的残片——没有它，整艘船都不完整。"

"但它也是最容易被发现的。"你说。

"对。"Echo说，"所以它藏在第一组——最显眼的位置，反而最难被怀疑。"

题目描述

$n$ 根木棍，长度已知。分成若干组，每组长度之和相等。求能否分成功。

输入格式

$n$，然后 $n$ 个长度。

输出格式

能否分成功。

输入样例

3 3 10

输出样例

2147483647

提示

• 先排序，从长到短逐根尝试放入各组。
• 剪枝：总和不能整除、当前和超过目标、重复状态跳过。

木棒分完后，森林中央出现了一道光柱。Echo飘到光柱前，投影被光芒切割成碎片。

"第五层。"她说。