사탕

Farmer John(농부 존)은 여러 날에 걸쳐 Bessie(소 베시)에게 나누어 줄 사탕 $N$개를 가지고 있다 ($1 \le N \le 40000$).

매일 Bessie는 정해진 목록에 있는 $N_{opt}$개의 선택지 $C_i$ 중 정확히 하나를 골라 그 개수만큼 사탕을 먹는다 ($1 \le N_{opt} \le 50$, $1 \le C_i \le N$). 남은 사탕이 $C_i$개 이상일 때에만 선택지 $i$를 골를 수 있으며, 고른 경우 정확히 $C_i$개를 먹는다. 더도 덜도 안 된다.

또한 Farmer John은 자신이 좋아하는 수 $F$개 $FN_i$를 알려 주었다 ($1 \le F \le 50$, $1 \le FN_i \le N$). 어느 날 사탕을 먹고 난 뒤 남은 사탕의 개수가 이 좋아하는 수 중 하나와 정확히 같아지면, Bessie는 Farmer John에게 사탕을 정확히 $M$개 더 넣어 달라고 요청할 수 있다 ($1 \le M \le 100$). 새로 늘어난 개수가 또다시 좋아하는 수와 같다면 다시 $M$개를 요청할 수 있고, 이런 식으로 반복할 수 있다. 요청은 언제든지 멈출 수 있다. 경우에 따라서는 Bessie가 사탕을 무한히 먹을 수도 있다.

남은 사탕으로 어떤 선택지도 고를 수 없고(어떤 $C_i$에 대해서도 사탕이 부족하고) 남은 개수가 좋아하는 수도 아니라면, Bessie는 더 이상 사탕을 먹을 수 없다.

Bessie는 앞을 멀리 내다보지 못하므로, 사탕을 최대한 많이 먹을 수 있도록 도와주어야 한다.

예를 들어, 바구니에 사탕이 10개 있고, Bessie가 매일 3개 또는 5개를 먹을 수 있으며, 남은 개수가 2 또는 4일 때마다 Farmer John이 사탕 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

이때 먹은 사탕의 총합은 $3 + 3 + 3 + 3 = 12$이다.

• 첫째 줄: 공백으로 구분된 네 정수 $N$, $N_{opt}$, $F$, $M$.
• 둘째 줄부터 $N_{opt}+1$번째 줄까지: 각 줄에 정수 $C_i$가 하나씩 주어진다.
• $N_{opt}+2$번째 줄부터 $N_{opt}+F+1$번째 줄까지: 각 줄에 정수 $FN_i$가 하나씩 주어진다.

제약: $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$.

• 정수 하나: Bessie가 먹을 수 있는 사탕의 최대 총 개수. 무한히 먹을 수 있으면 $-1$을 출력한다.