给定一个长度为 $n$ 的正整数数组 $a$ 和一个正整数 $x$。你可以随意重排该数组的所有元素。然后，你需要按照从第 $1$ 个到第 $n$ 个的顺序执行操作 $x \leftarrow x \pmod{a_i}$。
你的任务是重排数组，使得在执行完 $n$ 次操作后，$x$ 的值尽可能大。
输入格式
第一行包含一个整数 $n$ ($1 \le n \le 21$)，表示数组的长度。 第二行包含 $n$ 个空格分隔的正整数 $a_i$ ($1 \le a_i \le 10^{18}$)，表示数组的元素。 第三行包含一个整数 $x$ ($1 \le x \le 10^{18}$)，表示进行操作的初始数值。
输出格式
输出一行一个整数，表示操作后 $x$ 的最大可能值。
样例
样例输入 1
3 5 6 7 15
样例输出 1
3
样例输入 2
4 20 21 22 10 107
样例输出 2
9
样例输入 3
5 5 6 7 8 9 1000000000000
样例输出 3
4