Ser has recently set up many sweet factories and is all set to give many big businessmen a run for their money. On one of his regular inspection days, he visits a factory and finds $N$ different types of sweets prepared on that day. Each sweet has a taste value $T_{i}$. Ser asks his workers to prepare boxes of sweets, with each box containing a non-empty subset of sweets. The taste of each box is the sum of taste values of all sweets in that box.

Now, Ser asks his workers to stack up all boxes (there will be $2^N -1$ such boxes) from top to bottom in non-decreasing order of their tastes (i.e the box with maximum taste will be at the bottom). Suddenly, Ser's brother whom he fondly calls Big-B walks in and asks him how tasty is the $K^{th}$ box from the the top. Help Sir impress Big-B.

Input Format

The first line contains a number N denoting the number of different sweets.
Next line contains N space separated positive integers wherein the i'th integer represents $T_{i}$.
Next line contains K.

Output Format

Print a single integer, the taste of the $K^{th}$ box from the top.

Constraints

$1<=N<=30$

$1<=T_{i}<= 10^9$

$1<=K<= (2^N-1)$

Subtask 1 (10 points): $N<=20$

Subtask 2 (20 points): $N<=30$ , $T_{i} <= 10^4$

Subtask 3 (70 points): Original constraints