G. Massage Schedule
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Recently, Monocarp was appointed as a director of a bathhouse, and now he faces an unusual task — creating work schedules.

There are $$$n$$$ massage therapists working in the bathhouse in total, and the schedule of the $$$i$$$-th therapist is described by one positive integer $$$a_i$$$.

Also, currently $$$m$$$ visitors have signed up for massages. For each of them, Monocarp must choose a specific therapist and a day as a pair $$$(i, r)$$$, where $$$1 \le i \le n$$$ and $$$0 \le r \lt a_i$$$. This means that this visitor is assigned to the $$$i$$$-th therapist and will come to them on days $$$r, r + a_i, r + 2a_i$$$, and so on (days are counted from $$$0$$$).

Thus, $$$a_i$$$ is the period with which visitors come to the $$$i$$$-th therapist. No more than one visitor can be assigned to one therapist on the same day.

Monocarp wants to choose schedules for the visitors in such a way that the first day when at least two people come on the same day is as late as possible.

Input

The first line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of massage therapists.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the therapists' schedules.

The third line contains one integer $$$m$$$ ($$$1 \le m \le \sum{a_i}$$$) — the total number of visitors.

Output

Print one integer — the latest possible first day when at least two visitors come. If it is possible to choose schedules so that this never happens, print $$$-1$$$.

Examples
Input
2
1 3
4
Output
0
Input
2
3 1
3
Output
-1
Input
3
4 2 4
6
Output
2