Ô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:

• Dòng đầu tiên gồm số nguyên N, C, T (1 ≤ N, C ≤ 105 , 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 ≤105).

Kết quả: Ghi ra một số nguyên duy nhất là thời gian cần tìm.

Ví dụ:

Input

5 3 4 
5 8 3 10 7

Output

4

Nguồn