Bao vây
Xem dạng PDFThành lũy của tướng RELTIH bị ~n~ cánh quân tiến công. Các binh sĩ trung thành với vị tướng này đã không quản ngại hiểm nguy đoạt được kế hoạch tấn công của kẻ thù. Theo kế hoạch, cánh quân thứ ~i~ sẽ bắt đầu tấn công vào ngày ~a_i~ và sau đó cứ ~b_i~ ngày lại tấn công một lần, tức là các cuộc tấn công của cánh quân ~i~ diễn ra ở các ngày ~a_i, a_i+b_i, a_i+2 \times b_i, \ldots~
Mặc dù binh sĩ của tướng Petrein rất gan dạ và có tinh thần chiến đấu rất cao nhưng tướng Petrein hiểu rằng nếu không có quân tiếp viện thì quân đội của ông cũng chỉ chống trả được ~k~ lần tấn công của kẻ địch. Như vậy tòa thành sẽ bị thất thủ khi diễn ra cuộc tấn công thứ ~k+1~.
Yêu cầu: Cho các số nguyên ~n, k, a_i, b_i\left(0 \leq a i \leq 10^9, 1 \leq b_i \leq 10^9, 1 \leq n \leq 10^5\right.~, ~0 \leq k \leq 6 \cdot 10^9~ ). Hãy xác định ngày thành bị thất thủ nếu không có tiếp viện.
Dữ liệu:
- Dòng đầu tiên chứa ~2~ số nguyên ~n~ và ~k~;
- Dòng thứ ~i~ trong ~n~ dòng sau chứa ~2~ số nguyên ~a_i~ và ~b_i~.
Kết quả:
- Một số nguyên - ngày tòa thành sẽ bị thất thủ.
Ví dụ:
Sample Input
2 5
0 2
0 3
Sample Output
6
Chấm điểm:
- Có ~50%~ số test tương ứng ~50%~ số điểm có ~k \leq n \leq 1000~;
- ~50%~ số test còn lại có ~n \leq 10^5~.
Bình luận
cho hỏi bài này mình làm sao ạ