Candy

Farmer John has $N$ candies that he wants to give Bessie over some number of days ($1 \le N \le 40000$).

Each day, Bessie eats exactly one amount chosen from a fixed master list of $N_{opt}$ options $C_i$ ($1 \le N_{opt} \le 50$, $1 \le C_i \le N$). She may pick option $i$ only if at least $C_i$ candies remain, and she then eats exactly $C_i$ candies — no more, no less.

Farmer John has also disclosed $F$ of his favorite numbers $FN_i$ ($1 \le F \le 50$, $1 \le FN_i \le N$). Whenever the number of candies remaining at the end of a day (right after Bessie eats) exactly equals one of these favorite numbers, Bessie may have him add exactly $M$ more candies to the supply ($1 \le M \le 100$). If the new remaining count is again a favorite number, she may add $M$ again, and so on; she may stop adding at any time. In the best case Bessie can obtain an infinite amount of candy.

Bessie can no longer eat any candy once she cannot pick any option (not enough candies remain for any $C_i$) and the remaining count is not one of the favorite numbers.

Bessie cannot plan far ahead, so she needs your help to eat as many candies in total as possible.

For example, suppose the basket starts with 10 candies, Bessie may eat 3 or 5 candies each day, and Farmer John adds 1 candy whenever the remaining count is 2 or 4. One optimal sequence of choices is:

        Start of   Candies   Remaining   Bonus   End of
 Day    day        eaten     after eat   added   day
  1     10         3         7           0       7
  2      7         3         4           1       5
  3      5         3         2           1       3
  4      3         3         0           0       0

The total number of candies eaten is $3 + 3 + 3 + 3 = 12$.

• Line 1: four space-separated integers $N$, $N_{opt}$, $F$, and $M$.
• Lines $2$ to $N_{opt}+1$: line $i+1$ contains a single integer $C_i$.
• Lines $N_{opt}+2$ to $N_{opt}+F+1$: line $i+N_{opt}+1$ contains a single integer $FN_i$.

Constraints: $1 \le N \le 40000$, $1 \le N_{opt} \le 50$, $1 \le C_i \le N$, $1 \le F \le 50$, $1 \le FN_i \le N$, $1 \le M \le 100$.

• A single integer: the maximum total number of candies Bessie can eat, or $-1$ if she can eat an infinite amount of candy.