#P1651. 塔

题目描述

小明很喜欢摆积木,现在他正在玩的积木是由 NN 个木块组成的,他想用这些木块搭出两座高度相同的塔,一座塔的高度是搭建它的所有木块的高度和,并且一座塔至少要用一个木块。每个木块只能用一次,也可以不用。目前已知每块木块的高度,小明想知道在最终两个塔的高度相同的情况下,他所能搭的塔的最大高度是多少,你能帮助他吗?

输入格式

第一行为一个整数 NN,表示木块个数。

第二行是 NN 个整数,表示 NN 块木块的高度。

输出格式

仅一个整数,表示能搭建的塔的最大高度,若不能搭建两座相同高度的塔,则输出 -1

3
2 3 5
5

提示

对于 100%100\% 的数据,N50N \le 50 ,每块木块的高度 hh 满足 1h5000001 \le h \le 500000,所有木块的高度总和 500000\le 500000