회전 초밥

회전 초밥 음식점에서는 여러 종류의 초밥이 접시에 담겨 회전 벨트 위에 놓인다. 손님은 벨트 위의 접시 중 원하는 초밥을 골라 먹는다. 초밥 종류는 번호로 나타내며, 벨트 위에는 같은 종류의 초밥이 여러 접시 있을 수 있다.

새로 문을 연 음식점은 다음 두 가지 행사를 진행한다.

1. 벨트의 임의의 한 위치에서 시작해 연속한 k개의 접시를 먹으면 할인된 정액 가격을 적용한다.
2. 각 손님에게 초밥 종류 하나가 적힌 쿠폰을 준다. 1번 행사에 참여하면 쿠폰에 적힌 종류의 초밥 한 접시를 추가로 무료로 받을 수 있다. 그 종류의 초밥이 현재 벨트 위에 없어도 요리사가 새로 만들어 제공한다.

손님은 이 행사에 참여해 가능한 한 많은 종류의 초밥을 먹으려 한다. 예를 들어 k=4이고 쿠폰 번호가 30이라고 하자. 쿠폰을 고려하지 않으면 네 접시에서 서로 다른 초밥 4종류를 먹는 경우가 여러 가지 있다. 그중 (2, 7, 9, 25)를 고르면 쿠폰으로 30번 초밥을 추가로 받아 총 5종류를 먹을 수 있다.

벨트 상태, 메뉴의 초밥 종류 수, 연속해서 먹을 접시 수, 쿠폰 번호가 주어질 때 손님이 먹을 수 있는 서로 다른 초밥 종류 수의 최댓값을 구하시오.

첫째 줄에 회전 초밥 벨트의 접시 수 N, 초밥 종류 수 d, 연속해서 먹을 접시 수 k, 쿠폰 번호 c가 공백으로 구분되어 주어진다. 조건은 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ k ≤ 3,000, k ≤ N, 1 ≤ c ≤ d이다.

둘째 줄부터 N개의 줄에는 벨트의 한 위치에서 시작해 회전 방향으로 보았을 때 각 접시에 놓인 초밥의 종류 번호가 한 줄에 하나씩 주어진다. 각 번호는 1 이상 d 이하이다.

먹을 수 있는 서로 다른 초밥 종류 수의 최댓값을 하나의 정수로 출력한다.