NEVER FORGET

题目描述

• $\text{Hitori}$ 发现了 $n$ 个正整数 $a_1, a_2, \cdots, a_n$，它们构成了一个可重集合 $\rm{S}$ ，即 $\text{S} = \{ a_1 , a_2, \cdots, a_n \}$ ，且 $\forall a_i \in \text{S}, \ 1 \leq a_i \leq n$ 。

• $\text{Nijika}$ 取出了 $\text{S}$ 的所有非空子集，并告诉你，每个非空子集的价值等于该子集中所有元素的和，即对于 $\text{T} \subseteq \text{S} \ (\text{T} \neq \varnothing)$ ，其价值 $V_\text{T} = \sum\limits_{a_x \in \text{T}} a_x$ 。

• $\text{Ryo}$ 将 $\text{S}$ 所有非空子集的价值从小到大排序，排序后的价值构成了序列 $w_1, w_2, \cdots, w_{2 ^ n - 1}$ 。

• $\text{Ikuyo}$ 想问你，$w_{2 ^ {n - 1}}$ 等于多少？

输入

输入包括两行

第一行包括一个正整数 $n$

第二行包括 $n$ 个正整数 $a_1, a_2, \cdots, a_n$

输出

输出包括一行

第一行包括一个正整数 $w_{2^{n - 1}}$

输入样例

3
2 1 2

输出样例

3

样例解释

$\text{S}$ 的所有非空子集分别为 $\{2\}, \{1\}, \{2\}, \{2, 1\}, \{2, 2\}, \{1, 2\},\{2, 1, 2\}$ 。

价值分别为 $2, 1, 2, 3, 4, 3, 5$ 。

从小到大排序后为 $1, 2, 2, 3, 3 , 4, 5$ 。

故 $w_{2 ^ {n - 1}} = w_4 = 3$ 。

数据范围

• 对于 $50\%$ 的数据， $1 \leq n \leq 16$
• 对于 $70\%$ 的数据， $1 \leq n \leq 200$
• 对于 $100\%$ 的数据， $1 \leq n \leq 500, \ 1 \leq a_i \leq n$

题目背景 - 续

等着你的我

我在等着你

连无尽的明天

都能够穿过

停下脚步 回头看

叹息着无休止的今天

永远这种事 记忆什么的

明知道这些都是留存不下来的

我还是为此苦恼挠头

在心的角落里哭泣

想要请你记住那些

在高架桥下渡过的美好时光

我依然在后悔 有话没能说出口

落荒而逃的那天

我们手牵手

曾经那些难舍难分的感情

这就是我的一切了

但是连这些 现在都失去了

时过境迁 物是人非

明知道世事无常

我却依然苦恼地直挠头

悔恨着有话说不出口的今天

想要请你记住那些

在高架桥下渡过的美好时光

我依然在后悔 有话没能说出口 落荒而逃的那天

等着你的我

我在等着你

连无尽的明天都能够穿过

我今天也依然苦恼地挠头

一直在黯然伤心

我非你莫属

——《Re:Re:》