Giáo sư Y đã mua được rất nhiều mảnh vườn, các mảnh vườn của giáo sư mua được là những mảnh đất thẳng hàng nhau chạy dọc trên một trục đường thẳng. Giáo sư chọn ra mảnh vườn đầu tiên để trồng cây, các mảnh vườn này được đánh số theo thứ tự từ đến . Hiện tại đây đều là những mảnh đất trống. Kế hoạch trồng cây trên các mảnh vườn của giáo sư là một dãy cặp số . Theo kế hoạch này thì giáo sư sẽ trồng cây trên mỗi mảnh vườn trong mảng vườn đâu tiên, cây trên mỗi mảnh vườn trong mảnh vườn tiếp theo,
Ví dụ: Với thì số lượng cây trên các mảnh vườn giáo sư sẽ trồng là .
Do kế hoạch trồng cây là rất lớn nên giáo sư đã đầu tư mua một cái máy có thể trồng cây hàng loạt một cách tự động. Tuy là tự động nhưng cũng có những quy tắc nhất định. Cụ thể là mỗi lần vận hành, máy chỉ có thể trồng trên một đoạn liên tiếp các mảnh vườn hợp lệ, mỗi mảnh vườn trồng cây (), những cây đã có trước đó trên các mảnh vườn này sẽ bị loại bỏ (những lần vận hành khác nhau thì con số này có thể khác nhau).
Một đoạn liên tiếp các mảnh vườn hợp lệ là một đoạn các mảnh vườn có chỉ số từ đến mà là lũy thừa của (giả sử là ) và phải là bội của .
Chẳng hạn với thì ta có các đoạn hợp lệ là .
Vườn đã mua, máy đã sắm, kế hoạch trồng cây đã lập, nhưng chi phí mỗi lần vận hành máy khá tốn kém nên giáo sư nhờ các bạn lập kế hoạch vận hành máy để trồng số lượng cây theo kế hoạch của giáo sư sao cho số lần phải vận hành máy là ít nhất. Giáo sư hứa sẽ mời các bạn dự tiệc nếu các bạn giúp được giáo sư.
Dữ liệu vào:
Dòng đầu chứa ba số nguyên .
dòng tiếp theo, dòng thứ chứa hai số nguyên .
Dữ liệu ra:
Ghi ra một số nguyên duy nhất là số lần vận hành máy ít nhất.
Giới hạn:
Subtask : số điểm có
Subtask : số điểm có
Subtask : số điểm có
Subtask : số điểm có
Subtask : số điểm có
Subtask : số điểm không có ràng buộc gì thêm.
Ví dụ:
Dữ liệu vào:
3 3 2
1 1
2 2
5 1
Dữ liệu ra:
3
Giải thích:
Kế hoạch trồng cây của giáo sư là:
Vận hành lần : trồng cây trên đoạn , số cây tương ứng là
Vận hành lần : trồng cây trên đoạn , số cây tương ứng là
Vận hành lần : trồng cây trên đoạn , số cây tương ứng là
