409936: GYM103860 F Modulo

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.

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.

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

3
5 6 7
15

3

4
20 21 22 10
107

9

5
5 6 7 8 9
1000000000000

4