17133번 - 라쿤이 정보섬에 올라온 이유

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

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

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

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

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

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

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

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

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

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

두 번째 줄에는 N개의 정수 a₁, a₂, …, a_N (0 ≤ a_i < K) - a_i는 i번째 라쿤이 a_i의 솜사탕을 들고 있다는 걸 의미한다.

세 번째 줄에는 M개의 정수 w₁, w₂, …, w_M (1 ≤ w_j ≤ 10¹⁸) - w_j는 j번째 솜사탕 제품 한봉지의 무게를 의미한다.

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

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