라쿤이 정보섬에 올라온 이유

라쿤이 정보섬에 올라왔다!

숭실대에는 라쿤 $N$마리가 살고 있다. 이 라쿤들은 음식을 꼭 분수대에 온몸을 담가 씻어 먹는다. 어느 날 정보섬에 맛있는 솜사탕이 있다는 소문이 돌았다. 솜사탕은 $M$종류가 있고, 한 봉지의 무게는 종류마다 다르다. 각 종류의 솜사탕은 무한히 준비되어 있다.

우선 체험 삼아 솜사탕을 받아 온 라쿤들은 평소처럼 분수대로 향했다. 그런데 솜사탕을 물에 담그는 순간 일부가 흔적도 없이 사라졌고, 수중에는 $K$로 나눈 나머지만 남았다.

패닉에 빠진 라쿤들이 계속 솜사탕을 요구하는 사태를 막기 위해 정보섬은 간단한 서류를 요구한다. 서류에는 수중에 남은 솜사탕의 무게와 받고 싶은 솜사탕의 종류를 적는다. 서류를 제출하면 그 서류의 심사가 끝날 때까지 아무것도 할 수 없다. 내용이 완전히 같은 서류가 이미 제출된 적이 있으면, 설령 그 서류를 자신이 작성하지 않았더라도 심사에서 탈락한다. 심사를 통과한 라쿤에게는 해당 솜사탕 봉지가 지급되고, 라쿤은 이미 가지고 있던 솜사탕과 그것을 합친다. 그러고는 너무 기쁜 나머지 곧바로 분수대로 달려가 씻어 버린다.

또한 정보섬은 너굴스티커 제도를 시행하고 있다. 스티커가 붙은 서류는 붙지 않은 서류와 다른 것으로 취급된다. 스티커가 몇 개 붙었는지는 상관없이, 스티커가 붙었는지 여부만 확인한다. 스티커가 붙어 있고 내용이 같은 서류가 있으면 마찬가지로 탈락한다. 스티커는 무게 $R$만큼의 솜사탕으로 구입할 수 있다. 한 번에 여러 개를 사도 되고, 사 두고 붙이지 않아도 된다. 다만 스티커는 물에 매우 약해서, 분수대에서 솜사탕을 씻을 때마다 모두 사라진다.

요약하면 라쿤들은 다음 순서의 작업을 무한히 반복한다.

1. 스티커를 0개 이상 구매한다.
2. 서류를 작성한다.
3. 서류가 통과되었다면 솜사탕을 받아 씻는다.

받고, 씻고, 다시 받는다. 이 끝나지 않는 굴레 속에서 라쿤들의 대장 '낫너굴'이 제안을 했다. 라쿤신께서 점지해 주신 수 $A$에 대해, 솜사탕의 무게가 $A$가 되는 순간 더 가져오지 말고 먹자는 것이었다. 충격적인 제안에 라쿤들은 여기저기서 술렁였지만, 지금까지 겪은 고생을 떠올리고 곧 잠잠해졌다.

최대 몇 마리의 라쿤이 솜사탕을 먹을 수 있는지 구해 주자!

첫 번째 줄에 네 개의 정수 $N$, $M$, $K$, $R$이 주어진다 ($1 \le N \le 500$, $1 \le M \le 50$, $2 \le K \le 500$, $1 \le R < K$). $N$은 라쿤 수, $M$은 솜사탕 종류 수, $K$는 남은 솜사탕 무게를 나눌 때 쓰는 수, $R$은 스티커를 사기 위해 필요한 솜사탕의 무게다.

두 번째 줄에는 $N$개의 정수 $a_1, a_2, \ldots, a_N$이 주어진다 ($0 \le a_i < K$). $a_i$는 $i$번째 라쿤이 무게 $a_i$의 솜사탕을 들고 있다는 뜻이다.

세 번째 줄에는 $M$개의 정수 $w_1, w_2, \ldots, w_M$이 주어진다 ($1 \le w_j \le 10^{18}$). $w_j$는 $j$번째 솜사탕 제품 한 봉지의 무게다.

마지막 줄에는 라쿤신께서 점지해 주신 정수 $A$가 주어진다 ($0 \le A < K$).

솜사탕을 먹을 수 있는 라쿤이 최대 몇 마리인지 출력한다.