Chính phủ đang triển khai công trình trọng điểm quốc gia. Mỗi ngày công trình thứ tiêu hết triệu đồng.
Để hạn chế ảnh hưởng của suy thoái kinh tế, chính phủ quyết định tung ra gói kích cầu, mỗi gói có giá trị triệu đồng. Các gói kích cầu sẽ được ưu tiên chi cho các công trình trọng điểm. Gói kích cầu thứ sẽ bắt đầu được giải ngân từ ngày . Nếu nó được chi cho công trình thì sau ngày toàn bộ tiền của gói kích cầu được sử dụng hết, trong đó là số nguyên nhỏ nhất không nhỏ hơn . Mỗi gói kích cầu được chi trọn cho một công trình nào đó. Mỗi công trình có thể nhận được nhiều gói kích cầu, nhưng phải sử dụng lần lượt hết gói này đến gói khác, trong một ngày không được rút tiền từ quá một gói kích cầu. Có một số ràng buộc sử dụng gói kích cầu, cụ thể, có một số dự án không được dùng một số gói nào đó.
Các gói kích cầu phải được giải ngân hết càng sớm càng tốt. Thủ tướng chính phủ muốn các bộ phận chức năng cho biết thời hạn ngắn nhất giải ngân hết các gói kích cầu.
Ví dụ, với số công trình là , chi phí mỗi ngày cho mỗi công trình là và triệu đồng, có gói kích cầu, giá trị mỗi gói triệu, được phép giải ngân bắt đầu từ các ngày và không có ràng buộc sử dụng gói kích cầu thì sau ngày là thời ngắn nhất giải ngân hết các gói kích cầu.
Yêu cầu: Cho các số nguyên và và một số ràng buộc sử dụng gói kích cầu. Hãy xác định số ngày ít nhất cần thiết để giải ngân hết các gói kích cầu.
Dữ liệu:
Dòng đầu tiên chứa ba số nguyên và ;
Dòng thứ hai chứa số nguyên ;
Dòng thứ ba chứa số nguyên ;
Dòng thứ tư chứa số nguyên là số ràng buộc sử dụng gói kích cầu;
Tiếp theo là dòng, mỗi dòng chứa hai số nguyên có nghĩa là dự án không được sử dụng gói .
Kết quả;
Một số nguyên là số ngày ít nhất cần thiết để giải ngân hết các gói kích cầu.
