Hiện nay, dịch bệnh COVID đang diễn biến vô cùng phức tạp và nguy hiểm, bên cạnh việc triển khai các biện pháp phòng chống dịch bệnh, Bộ Y tế nước ta còn có kế hoạch nhập các loại vắc-xin để tiêm phòng cho người dân.
Trong giai đoạn đầu của kế hoạch, có trường học cần cấp vắc-xin. Bộ Y tế nhận được danh sách gồm lô vắc-xin được đánh số từ đến , lô thứ có liều vắc-xin. Nhân viên của Bộ Y tế muốn chọn một hoặc một số lô liên tục nhau trong danh sách để cấp cho các trường sao cho tổng số liều vắc-xin trong các lô được chọn phải chia đều được cho trường.
Hãy xác định xem các nhân viên của Bộ Y tế có bao nhiêu cách khác nhau để chọn các lô vắc-xin. Hai cách chọn gọi là khác nhau nếu khác nhau điểm đầu hoặc điểm cuối hay cả hai. Ví dụ, với và số liều vắc-xin trong các lô lần lượt là ta có cách chọn (như hình bên dưới).
Trong số các cách chọn thỏa mãn yêu cầu, hãy tìm cách chọn mà số lô được chọn là nhiều nhất.
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên và ;
Dòng thứ hai chứa số nguyên dương .
Các số trên một dòng cách nhau một dấu cách.
Kết quả:
Dòng thứ nhất chứa một số nguyên là số cách chọn khác nhau. Nếu không tồn tại cách chọn thì kết quả sẽ là .
Nếu có cách chọn thì dòng thứ hai chứa một số nguyên dương là số lô vắc-xin trong cách chọn nhiều lô nhất thỏa mãn yêu cầu bài toán.
Ví dụ:
Dữ liệu:
10 4
15 50 225 60
Kết quả:
4
4
Giới hạn:
Subtask số điểm của bài có ;
Subtask số điểm khác có ;
Subtask số điểm khác có ;
Subtask số điểm còn lại không có ràng buộc bổ sung.
