Cồn Vành (thuộc huyện Tiền Hải, tỉnh Thái Bình cũ nay thuộc xã Hưng Phú, tỉnh Hưng Yên) là khu vực cửa sông ven biển với hệ sinh thái rừng ngập mặn phong phú và những hàng phi lao chắn cát trải dài. Rừng cây phi lao không những là nơi chắn gió, chắn cát mà còn cung cấp gỗ giúp người dân dựng nhà, làm vật dụng.

Qua nghiên cứu của các kỹ sư lâm nghiệp, các cây phi lao lớn rất đều, mỗi ngày chiều cao của mọi cây đều tăng thêm đúng ~1~ cm. Để phục vụ công việc của mình, ban quản lý cần một lượng gỗ với tổng chiều dài ít nhất là ~m~ (cm) được khai thác từ khu rừng nói trên.

Quy tắc khai thác như sau:

• Chỉ được cắt khi cây có chiều cao lớn hơn ~c~ (cm) để đảm bảo mỹ quan và phần gốc còn lại vẫn đủ sức chắn gió, chắn cát.
• Để bảo tồn mật độ rừng, chỉ được phép khai thác tối đa ~k~ cây.

Yêu cầu

Trong một khu rừng có ~n~ cây phi lao, cây thứ ~i~ có độ cao ~a_i~. Hãy tính xem sau ít nhất bao nhiêu ngày (tính từ ngày ~0~) thì ban quản lý có thể khai thác để thu được lượng gỗ không nhỏ hơn ~m~ (cm) theo quy tắc trên?

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng 1: Bốn số nguyên dương ~n, m, k, c~ ~(1 \le k \le n \le 10^5; 0 \le m \le 10^{18}; 1 \le c \le 10^{18})~, giữa các số có một dấu cách;
• Dòng 2: ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ là chiều cao (cm) ban đầu của các cây trong khu rừng ~(1 \le a_i \le 10^{12})~.

Dữ liệu đầu ra

Ghi ra một số nguyên là số ngày ít nhất cần thiết. Nếu ngày ~0~ đã có thể khai thác đủ lượng gỗ ~m~ thì in ra ~0~.

Ràng buộc dữ liệu

• Subtask 1 (40% số điểm): ~1 \le m, c \le 10^4~ và ~1 \le k \le 100~;
• Subtask 2 (30% số điểm): ~1 \le m \le 10^8~ và ~1 \le k \le 10^4~;
• Subtask 3 (30% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

3 5 2 4
10 4 1

OUTPUT

0

Giải thích: Được chọn tối đa ~2~ cây cho gỗ nhiều nhất. Ngày ~0~: Hai cây cao nhất có chiều cao là ~10~ và ~4~. Lượng gỗ thu được lần lượt là ~(10-4) + (4-4) = 6~, tổng bằng ~6 > 5~ nên đáp án là ~0~.

Ví dụ 2

INPUT

6 25 3 10
9 9 20 15 1 8

OUTPUT

4

Giải thích: Được chọn tối đa ~3~ cây cao nhất để khai thác là ~20, 15~ và ~9~. Ngày ~0~: Lượng gỗ thu được là ~(20-10) + (15-10) + 0 = 15~ ~(15 < 25)~ nên chưa đủ gỗ. Với số ngày là ~4~, tổng gỗ là ~(24 - 10) + (19 - 10) + (13 - 10) = 26 > 25~ nên đủ lượng gỗ và đáp án là ~4~.