Rotating Sushi

In a rotating sushi restaurant, plates of many sushi types are placed on a moving belt. A customer chooses the sushi they want from the belt. Each sushi type is represented by a number, and the belt may contain more than one plate of the same type.

A newly opened restaurant is running the following two promotions.

1. If a customer starts at any position on the belt and eats k consecutive plates, those plates are offered for a fixed discounted price.
2. Each customer receives a coupon for one sushi type. When the customer joins the first promotion, they may receive one extra plate of the coupon sushi type for free. If that type is not currently on the belt, the chef makes it and serves it separately.

A customer wants to eat as many different sushi types as possible through this promotion. For example, suppose k=4 and the coupon number is 30. Without the coupon, there are several choices of four consecutive plates that contain 4 different types. If the customer chooses (2, 7, 9, 25), the coupon can add sushi type 30, for a total of 5 different types.

Given the state of the belt, the number of sushi types on the menu, the number of consecutive plates to eat, and the coupon number, compute the maximum number of different sushi types the customer can eat.

The first line contains four integers N, d, k, and c: the number of plates on the belt, the number of sushi types, the number of consecutive plates to eat, and the coupon number. The constraints are 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ k ≤ 3,000, k ≤ N, and 1 ≤ c ≤ d.

Each of the next N lines contains one integer between 1 and d, representing the sushi type on each plate when following the belt from some position in its rotating direction.

Print one integer: the maximum number of different sushi types the customer can eat.