AZIR HOÀNG ĐẾ CÁT

ĐỀ BÀI: AZIR — ĐẾ CHẾ CÁT

Trong một trận đấu League of Legends, Azir triệu hồi \(N\) lính cát xếp thành một hàng ngang từ vị trí \(1\) đến \(N\). Lính cát thứ \(i\) có sức mạnh là \(A_i\).

Azir muốn phân chia toàn bộ \(N\) lính cát thành một số cuộc tấn công liên tiếp. Một cách chia hợp lệ cần thỏa mãn các điều kiện:

1. Mỗi cuộc tấn công gồm một đoạn lính cát liên tiếp.
2. Mỗi cuộc tấn công chứa không quá \(M\) lính cát (độ dài đoạn \(\le M\)).
3. Tổng sức mạnh của các lính cát trong mỗi cuộc tấn công ít nhất bằng \(K\) (tổng đoạn \(\ge K\)).

Yêu cầu: Tìm số cuộc tấn công ít nhất cần thực hiện để chia hết \(N\) lính cát. Nếu không tồn tại cách chia thỏa mãn, in ra -1.

Dữ liệu vào:

• Dòng 1: Chứa ba số nguyên \(N, M, K\) (\(1 \le M \le N \le 2 \times 10^5, 1 \le K \le 10^{18}\)).
• Dòng 2: Chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^9\)).

Kết quả ra:

• In ra một số nguyên duy nhất là số cuộc tấn công ít nhất, hoặc -1 nếu không có cách chia hợp lệ.

Ví dụ:

Input

6 3 10
4 6 5 5 2 8

Output

2

Giải thích:

• Cuộc tấn công 1: \([4, 6, 5]\) (Độ dài \(3 \le 3\), Tổng \(= 15 \ge 10\)).
• Cuộc tấn công 2: \([5, 2, 8]\) (Độ dài \(3 \le 3\), Tổng \(= 15 \ge 10\)).
• Số cuộc tấn công ít nhất là \(2\).