시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 16 8 8 61.538%

문제

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

아무도 모르는 사실이지만, 숭실대에는 라쿤 N 마리가 살고 있다!!! 깔끔한 라쿤들은 어디선가 과일이나 채소를 구했고, 구한 음식은 꼭 분수대에서 씻어서 먹었다. 그러던 어느 날, 정보섬에서 맛있는 솜사탕을 나눠준다는 소문이 돌기 시작했다. 우선 체험 차, 솜사탕을 받아온 라쿤들은 분수대로 향했다. 솜사탕을 물에 담그는 순간, 솜사탕은 K로 나눈 나머지 만을 남기고 흔적도 없이 사라져 버렸다! 즉, 손에는 오직 mod K만큼의 솜사탕만이 남아버린 것이다. 라쿤들은 당황했지만, 솜사탕을 더 받아오기로 했다.

패닉에 빠진 라쿤들이 계속 솜사탕을 요구하는 사태를 막기 위해서, 정보섬은 간단한 서류를 요구한다. 서류는 현재 손에 남아있는 솜사탕 무게, 그리고 받고 싶은 솜사탕 번호를 쓰게 되어 있다. 만약 이전에 정확히 똑같은 서류가 제출된 기록이 있을 경우, 서류 심사에서 탈락한다. 결국, 탈락한 라쿤은 솜사탕을 받을 수 없다. 물론 다른 라쿤이 제출했던 서류라도 마찬가지며, 서류 심사중에는 다른 서류가 제출될 수 없다.

서류를 통과한 라쿤은, 서류에 작성했던 솜사탕 한 봉지를 받아 이미 가지고 있던 솜사탕과 합친다. 솜사탕 종류별로 한 봉지의 무게는 정해져 있고, 정보섬에 보관된 솜사탕은 무한히 많다. 라쿤은 솜사탕을 받는 순간 너무 기쁜 나머지, 분수대로 달려가 씻어 버린다는 점에 주의하자.

추가로 정보섬은 너굴스티커 제도를 시행한다. 어떤 서류에 스티커를 붙여 제출한다면, 이미 똑같은 서류가 제출되어 있더라도 솜사탕을 받아올 수 있다. 더 정확히는, 스티커가 붙어있는 서류만 따로 검사한다. 따라서 기존과 마찬가지로, 이미 스티커가 붙은 똑같은 서류가 제출되어 있다면, 솜사탕을 받을 수 없다. 스티커는 무게 R만큼의 솜사탕으로 구입할 수 있고, 몇번을 사도, 그리고 사용하지 않아도 괜찮다. 다만 스티커가 매우 물에 약하기 때문에, 분수대에서 솜사탕을 씻을 때마다 모두 사라져버린다.

솜사탕을 최대한 많이 먹고 싶은 라쿤들은 다음과 같은 순서의 작업을 무한히 반복할 수 있다!

1. 0개 이상의 스티커를 구매한다.
2. 서류를 작성한다. (스티커는 붙일 수도 안붙일 수도 있다)
3. 만약 서류에 통과되었다면, 솜사탕을 받아 씻는다.

솜사탕을 받고, 분수대에 씻고, 솜사탕을 받고... 이 영겁의 굴레 속에서, 라쿤들의 대장 '낫너굴'은 하나의 제안을 했다. 라쿤신께서 점지해 주신 수 A에 대해, 씻고 난 솜사탕의 무게가 A일 경우, 솜사탕을 더 가져오지 말고 먹자는 것이었다. 매우 충격적인 제안에 당황한 듯, 라쿤들은 여기저기 술렁거렸지만 곧 지금까지 경험한 고생을 떠올리고 잠잠해졌다.

라쿤신께서 점지해 주신 수 A와 라쿤들이 현재 들고 있는 솜사탕 무게가 주어졌을 때, 최대 몇 마리의 라쿤이 솜사탕을 먹을 수 있을지 구해 주자!

입력

첫 번째 줄에는 네 개의 정수 N, M, K 그리고 R이 주어진다. (1 ≤ N ≤ 500, 1 ≤ M ≤ 50, 2 ≤ K ≤ 500, 1 ≤ R < K) - N, M, K, R은 차례대로 라쿤 수, 솜사탕 종류, 솜사탕이 남는 나머지 수, 스티커를 사기 위해 필요한 솜사탕의 무게를 의미한다.

두 번째 줄에는 N개의 정수 a1, a2, , aN (0 ≤ ai < K) - aii번째 라쿤이 ai의 솜사탕을 들고 있다는 걸 의미한다.

세 번째 줄에는 M개의 정수 w1, w2, , wM (1 ≤ wj ≤ 1018) - wjj번째 솜사탕 제품 한봉지의 무게를 의미한다.

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

출력

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

예제 입력 1

3 2 10 9
0 9 9
1 1
2

예제 출력 1

2

예제 입력 2

4 1 2 1
0 1 0 1
64
0

예제 출력 2

4