4324: T2 石头称重（stone）
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
## T2 石头称重（stone）
### 题目描述
小 E 有 $n$ 块石头，编号从 $1$ 到 $n$。第 $i$ 号石头的重量是正整数 $w_i$。
对于每一个 $i$，我们保证编号为 $i$ 的石头比所有编号小于 $i$ 的石头的重量总和还要重。
小 E 有时会在使用天平秤称量物体时运用他收集的石头：他将物体放在一个盘子上，将一些石头放在另一个盘子上，如果两个盘子处于平衡状态，他就知道物体的重量与石头组合的重量相同。
当然，并不是所有的物体都可以用上述方法来称重：有时不存在与该物体重量相同的石头组合。
如果可以用一些石头的组合（可能是空集）来平衡重量为 $x$ 的物体，则称重量 $x$ 是可接受的。
例如，如果小 E 拥有的石头重量为 $3$ 和 $6$，则可接受的重量有 $0,3,6,9$。
对于给定的 $n$ 块石头，考虑所有不同的可接受重量的严格递增序列，请求出此序列中第 $k$ 个元素的重量是多少。如果不存在第 $k$ 个元素，则输出 $-1$。
输入
### 输入格式
输入的第一行，包含一个正整数 $n$，表示石头的数量。
输入的第二行，包含 $n$ 个正整数，表示每个石头的重量。
输入的第三行，包含一个正整数，表示题目中所给出的 $k$。
输出
### 输出格式
输出共一行，包含一个整数，即可接受重量的第 $k$ 个元素，若不存在则输出 $-1$。
样例输入 复制
2
4 7
1样例输出 复制
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}$。