题目描述

在这道题中，我们规定集合中允许出现重复元素。

给定 $n$ 个整数 $a_1,a_2,\cdots, a_n$ 和一个参数 $k$，这些数可以组成 $2^{n}-1$ 个集合（不算空集）。

请分别计算这些集合的元素之和，请从中找到第 $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$ 小的和。

3
2 3 3
4

5

数据范围

• 对于 $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)$