Bài 4

Ông John có N bịch kẹo. Bịch kẹo thứ i chưa Pi viên kẹo. Ông John sẽ đi phát kẹo cho C đứa trẻ. Mỗi đứa trẻ trong 1 giây có thể ăn được T viên kẹo. Do tuổi già, ông John muốn chia hết số kẹo cho các đứa trẻ sao cho thời gian ăn hết số kẹo ông chia của đứa trẻ ăn lâu nhất là nhỏ nhất. Biết rằng mỗi đứa trẻ sẽ được chia những bịch kẹo là liên tiếp nhau và mỗi bịch kẹo chỉ được duy nhất 1 đứa trẻ ăn. Nếu giây cuối cùng chỉ còn X viên kẹo với X < T thì vẫn tính là ăn trong vòng 1 giây.

Dữ liệu: Cho từ tệp văn bản BAI4.INP gồm:

• Dòng đầu tiên gồm số nguyên N, C, T (1 ≤ N, C ≤ 10^5 , 1 ≤ T ≤ 50).

• Dòng tiếp theo chưa N số nguyên. Số nguyên thứ i biểu thị cho Pi (1 ≤ Pi ≤10^5).

Kết quả: Ghi vào tệp văn bản BAI4.OUT

• Một số nguyên duy nhất là thời gian cần tìm.

Ví dụ

BAI3.INP       BAI3.OUT
5 3 4 
5 8 3 10 7       4 

Giải thích • Đứa trẻ đầu tiên ăn 2 bịch kẹo đầu tiên hết 4 giây.

• Đứa trẻ thứ 2 ăn bịch kẹo thứ 3 hết 3 giây.

• Đứa trẻ cuối cùng ăn bịch kẹo 4 hết 2 giây.

*Chấm điểm *

• Có 50% số test: 1 ≤ N, C ≤ 1000

• Có 50% số test: Không có ràng buộc gì thêm.