F. Modulo
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a 1-indexed positive integer array $$$a$$$ of length $$$n$$$ and a positive integer $$$x$$$. You can rearrange all elements of this array as you wish. Then you should perform the operation $$$x \leftarrow x \bmod a_i$$$ in order from $$$1$$$-th to $$$n$$$-th.

Your task is to rearrange the array in such a way that $$$x$$$ is the maximum possible after $$$n$$$ operations.

Input

The first line contains one integer $$$n$$$ ($$$1 \le n \le 21$$$) — the length of the array.

The second line contains $$$n$$$ space-separated positive integers $$$a_i$$$ ($$$1 \le a_i \le 10^{18}$$$) — the elements of the array.

The third line contains one integer $$$x$$$ ($$$1 \le x \le 10^{18}$$$) — the number to perform operations.

Output

Print a single integer in one line — the maximum value of $$$x$$$ to the problem.

Examples
Input
3
5 6 7
15
Output
3
Input
4
20 21 22 10
107
Output
9
Input
5
5 6 7 8 9
1000000000000
Output
4