当前没有测试数据。

题目描述

应明澈喜欢玩石头，经常沉迷于找石头之中无法自拔，所以学习成绩一落千丈。他 有 (n) 块石头，编号从 (1) 到 (n)。第 (i) 号石头的重量是正整数 (w_i)。

对于每一个 (i)，我们保证编号为 (i) 的石头比所有编号小于 (i) 的石头的重量总和还要重。

应明澈 有时会在使用天平秤称量物体时运用他收集的石头：他将物体放在一个盘子上，将一些石头放在另一个盘子上，如果两个盘子处于平衡状态，他就知道物体的重量与石头组合的重量相同。

当然，并不是所有的物体都可以用上述方法来称重：有时不存在与该物体重量相同的石头组合。

如果可以用一些石头的组合（可能是空集）来平衡重量为 (x) 的物体，则称重量 (x) 是可接受的。

例如，如果应明澈 拥有的石头重量为 (w_1) 和 (w_2)，则可接受的重量有 (0, w_1, w_2, w_1 + w_2)。

对于给定的 (n) 块石头，考虑所有不同的可接受重量的严格递增序列，请求出此序列中第 (k) 个元素的重量是多少。如果不存在第 (k) 个元素，则输出 (-1)。

输入格式

输入的第一行，包含一个正整数 (n)，表示石头的数量。

输入的第二行，包含 (n) 个正整数，表示每个石头的重量。

输入的第三行，包含一个正整数 (k)。

输出格式

输出共一行，包含一个整数，即可接受重量的第 (k) 个元素，若不存在则输出 (-1)。

样例

• 样例 1 输入

2
4 7
1

• 样例 1 输出

0

• 样例 2 输入

5
1 3 7 13 30
10

• 样例 2 输出

14