题目描述

房间里有 $n \ (1 \le n \le 40000)$ 个糖果， Bessie 每次吃掉糖果数 $x$ 必须为 $C$ 序列的某个数，$C$ 序列有 $cn$ 个数。

当Bessie每次吃掉糖果后剩余的糖果数是 $F$ 序列的某个数时，房间内可以增加 $m$ 个糖果（当然 Bessie 也可以选择不增加）。如果增加后房间内的糖果数，还是 $F$ 序列的某个数，就可以继续添加 $m$ 个糖果（当然 Bessie 也可以选择不增加）。

在最好的情况下，Bessie可以吃掉无限量的糖果！

求Bessie最多可以吃几个。

输入格式

第一行四个整数 $n, cn, fn, m \ ( 1 \le cn,fn \le 50 ,1 \le m \le 50)$

下来 $C$ 序列 的 $cn$ 个数。

下来 $F$ 序列 的 $fn$ 个数。

输出格式

一个整数，表示 Bessie 最多可以吃几个。

如果 Bessie 可以无限量吃糖输出 -1。

输入输出样例 #1

输入 #1

10 2 2 1 
3 
5 
4 
2

输出 #1

12