Description

FJ 知道贝茜喜欢吃糖果。FJ 有 $N (1 \le N \le 40000)$ 颗糖果，他想在若干天内将这些糖果送给贝茜。每一天，FJ 会让贝茜从他提供的一个列表中选择她当天想吃多少糖果，该列表有 $Nopt(1 \le Nopt \le 50)$ 种不同的选项 $C_i (1 \le C_i \le N)$ 。她必须恰好拿走 $C_i$ 颗糖果。

农夫约翰给出了 $F(1 \le F \le 50)$ 个他喜欢的数字 $FN_i (1 \le FN_i \le N)$ 。每当一天结束时，如果剩余的糖果数量恰好等于这些数字之一，贝茜可以选择添加 $M（1 \le M \le 100)$ 颗糖果。如果添加糖果后又出现了另一个 FJ 喜欢的数字，贝茜可能会再次获得添加 $M$ 颗糖果的机会。在最好的情况下，贝茜可以获得无限多的糖果！

当贝茜无法在列表中选择糖果数量（因为糖果不够）时，她就无法再获得更多糖果。

不幸的是，贝茜不知道该如何规划才能吃掉尽可能多的糖果，所以她需要你的帮助。

举例来说，考虑以下场景：

• FJ 最初有 $10$ 颗糖果
• 贝茜每天可以选择吃掉 $3$ 或 $5$ 颗糖果
• 当剩余的糖果数量是 $2$ 或 $4$ 时，FJ 会添加 $1$ 颗糖果

贝茜可以使用以下选择来最大化她能吃掉的糖果数量：

                  初始糖果数     吃掉糖果数     剩余糖果数     奖励糖果数     最终糖果数
        第1天        10            3            7             0            7
        第2天         7            3            4             1            5
        第3天         5            3            2             1            3
        第4天         3            3            0             0            0

Input Format

• 第 $1$ 行：四个由空格分隔的整数：$N,Nopt,F,M$
• 第 $2$ 行到第 $Nopt+1$ 行：第 $i+1$ 行包含一个整数：$C_i$
• 第 $Nopt+2$ 行到第 $Nopt+F+1$ 行：第 $i+Nopt+1$ 行包含一个整数：$FN_i$

Output Format

• 第 $1$ 行：一个整数，表示贝茜能吃掉的最大糖果数量，如果贝茜能吃掉无限多的糖果，则输出 -1。

10 2 2 1 
3 
5 
4 
2 

12