题目描述
给定 $n$ 个整数 $a_1,a_2,\cdots, a_n$ 和一个参数 $k$，这些数可以组成 $2^{n}-1$ 个集合（不算空集）。由于 $a_i$ 可能重复，为方便起见，规定它们组成的集合中允许出现重复的元素。
对这个集合，请分别计算它每个子集的元素之和，请从中找到第 $k$ 小的子集和。
例如对于 $2,3,3$ 来说，可以组成的子集有
$$\{2\}, \{3\}, \{3\}, \{2,3\}, \{2,3\}, \{3,3\}, \{2,3,3\}$$
它们的和分别为
$$2, 3, 3, 5, 5, 6, 8$$
当 $k=4$ 时，第 $k$ 小的子集的和是 $5$。
输入
+ 第一行：单个整数 $n$；
+ 第二行：$n$ 个整数 $a_1,\dots,a_n$；
+ 第三行：单个整数 $k$。
输出
单个整数：表示第 $k$ 小的子集和。
样例输入输出
提示
- 对于 $30\%$的数据，$1 \leq n \leq 20$
- 对于 $60\%$的数据，$1 \leq n \leq 10^3$
- 对于 $100\%$的数据，$1 \leq n \leq 10^5$ , $1 \leq a_i \leq 10^9$,$1 \leq k \leq min(2^n,10^6)$