题目描述

强哥的学校正在举办一场有趣的科学实验活动，活动中需要使用一些标准砝码来测量物体的重量。学校准备了 $n$ 个标准砝码，编号从 $1$ 到 $n$。第 $i$ 号砝码的重量是正整数 $w_i$。

这些砝码有一个特殊的性质：对于每一个 $i$，编号为 $i$ 的砝码比所有编号小于 $i$ 的砝码的重量总和还要重。

在实验过程中，强哥使用天平秤来称量物体：他将物体放在一个托盘上，将一些砝码放在另一个托盘上，如果两个托盘保持平衡，他就知道物体的重量等于所选砝码的总重量。

当然，并不是所有的重量都能用这种方法测量出来：有时候可能找不到一组砝码的组合重量正好等于某个物体的重量。

如果一个重量 $x$ 能够通过选择一些砝码（可能不选任何砝码）来平衡，我们就称这个重量 $x$ 是可测量的。

例如，如果强哥使用的砝码重量为 $3$ 和 $6$，那么可测量的重量有 $0, 3, 6, 9$。

现在的问题是：对于给定的 $n$ 个砝码，考虑所有不同的可测量重量并按从小到大的顺序排列，请求出这个序列中第 $k$ 个重量是多少。如果不存在第 $k$ 个重量，则输出 $-1$。

输入格式

输入的第一行包含一个正整数 $n$，表示砝码的数量。

输入的第二行包含 $n$ 个正整数，表示每个砝码的重量。

输入的第三行包含一个正整数 $k$，表示题目中要求的位置。

输出格式

输出一行，包含一个整数，即可测量重量序列中的第 $k$ 个元素，如果不存在则输出 $-1$。

样例 1 输入

2
4 7
1

样例 1 输出

1

样例 2 输入

5
1 3 7 13 30
10

样例 2 输出

14

数据规模与约定

• 对于 $40\%$ 的数据，保证 $n \le 8$。
• 对于另 $30\%$ 的数据，保证 $k \le 1000$。
• 对于 $100\%$ 的数据，保证 $1 \le n \le 50$，$1 \le k \le 1 \times 10^{18}$，$\sum_{j=1}^{i-1} w_j < w_i$，$\sum_{i=1}^n w_i \le 10^{18}$。