你在⼀个岛屿上，这个岛屿有⼀个神秘的巨石阵，据说在这个巨石阵中隐藏着传说中的宝藏。这个巨石阵由 n 块石头组成，每块石头的重量都是正整数。你得到了⼀份任务，需要把这些石头尽可能多的粉碎，找到隐藏在其中的宝藏。

你得到了⼀台石头破碎机，每⼀回合，你可以从中选出两块石头，然后将它们⼀起粉碎。如果这两块石头的重量相同，那么这两块石头都会被完全粉碎；如果它们的重量不同，那么假 设石头的重量分别为 x 和 y ，且 x \leq y ，那么粉碎的可能结果如下：

如果 x 等于 y ，那么两块石头都会被完全粉碎；

如果 x 不等于 y ，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y - x 。

你想要尽可能地找到隐藏在其中的宝藏，因此让最后剩余的石块的重量尽可能小。

你决定编写⼀个程序，帮助你计算出最后剩下的最后的石头重量，如果没有石头剩下，就返回 0。

输入两行：

第一行包含一个整数 n ，代表有 n 个石块；

第二行包含 n 个整数，代表每个石块的重量，以空格隔开。

一行，包含⼀个整数，代表剩余的石块的重量。

【样例 1 解释】

先选出重量为 7 和 8 的两个石块进行粉碎，得到重量为 1 的石块，所以留下的石块重量分别为：2、4、1、1、1，

再选出重量为 2 和 4 的两个石块进行粉碎，得到重量为 2 的石块，所以留下的石块重量分别为：2、1、1、1，

接着选出重量为 2 和 1 的两个石块进行粉碎，得到重量为 1 的石块，所以留下的石块重量分别为：1、1、1，

最后任意选出重量为 1 的两个石块，将两个石块都粉碎，最终留下的石块重量为：1 。

这就是最后剩下那块石头的重量。

【数据说明】

对于 100\% 的数据，满足 1 \leq n \leq 30，1 \leq 每个石块的重量 \leq 1000。

23年泰州市赛

市赛贪心