Maximizing Candy Consumption

Farmer John has $$N$$ candies and wants to distribute them to Bessie over several days. Each day, Bessie must eat exactly one of the amounts given in a master list of $$N_{opt}$$ options, where each option is denoted by $$C_i$$ and satisfies $$1\le C_i\le N$$.

After Bessie eats her candies for the day, if the number of candies remaining equals one of Farmer John’s favorite numbers $$FN_i$$ (for $$1\le i \le F$$), then she has the option to have him add exactly $$M$$ more candies to the supply. Moreover, if after adding $$M$$ candies the total still equals one of his favorite numbers, she may choose to have another $$M$$ candies added – and she may do so repeatedly. In the best circumstances, Bessie can obtain an infinite amount of candy!

The process stops when Bessie cannot remove any valid amount (because there aren’t enough candies) and the remaining candy count is not one of Farmer John’s favorite numbers.

Your task is to determine the maximum number of candies Bessie can eat. If there is a sequence of moves that lets her eat an unbounded (infinite) number of candies, output -1.

inputFormat

The first line contains four integers: $$N$$, $$N_{opt}$$, $$M$$, and $$F$$, where

• $$1\le N\le 40000$$
• $$1\le N_{opt}\le 50$$
• $$1\le M\le 100$$
• $$1\le F\le 50$$

The second line contains $$N_{opt}$$ integers: $$C_1, C_2, \dots, C_{N_{opt}}$$, each between $$1$$ and $$N$$, representing the possible amounts Bessie can choose to consume in one day.

The third line contains $$F$$ integers: $$FN_1, FN_2, \dots, FN_F$$, each between $$1$$ and $$N$$, representing Farmer John’s favorite numbers.

outputFormat

Output a single integer — the maximum number of candies Bessie can eat. If Bessie can eat an infinite amount of candy, output -1.

sample

10 2 1 2
3 5
2 4

12