Ông John có ~N~ bịch kẹo. Bịch kẹo thứ ~i~ chứa ~P_i~ 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

• 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 ~P_i\ (1≤ P_i ≤10^5)~.

Kết quả

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

Ví dụ

Sample Input 1

5 3 4
5 8 3 10 7

Sample Output 1

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

• Subtask 1 (50% số test): ~1≤ N,C ≤1000~
• Subtask 2 (50% số test): Không có ràng buộc gì thêm.

Nguồn: Free Contest