Công ty phần mềm trò chơi SAGA vừa đưa lên trang web của mình trò chơi mới Saga Phantom rất hấp dẫn. Cứ sau ~c~ phút một bàn mới được bổ sung lên mạng. Người chơi đã vượt qua mọi bàn hiện có sẽ được xếp hàng chờ cung cấp bàn mới. Cứ mỗi phút server lại gửi bản cập nhật đến cho một khách hàng đang chờ trong dòng xếp hàng. Thời điểm cập nhật tính từ ~0~ đến ~c~. Khi người chơi vượt qua một bàn, phần mềm hệ thống sẽ ghi nhận thời điểm kết thúc ~t_i~ và đưa người đó vào dòng xếp hàng chờ đợi. Tại một thời điểm có thể có nhiều người cùng kết thúc cùng được đưa vào xếp hàng. Hết phiên giao dịch ~c~ phút đồng hồ hệ thống lại trở về ~0~. Những người trong hàng ở phiên giao dịch cũ vẫn được giữ lại và được tiếp tục phục vụ như bình thường. Việc cập nhật được thực hiện với độ trễ ~c~ phút, tức là sau ~c~ phút chương trình cập nhật mới bắt đầu đọc dòng xếp hàng đã ghi nhận trong khoảng ~c~ phút trước đó và xử lý y như bây giờ mới ghi nhận được yêu cầu.
Steve đã bẻ khóa được phần mềm cập nhật, nhưng không muốn lạm dụng điều đó làm ảnh hưởng nhiều đến những người chơi khác và gây sự chú ý của bộ phận bảo mật. Chính vì vậy Steve quyết định sẽ chèn yêu cầu của mình vào dòng xếp hàng sao cho thời gian chờ đợi là nhỏ nhất. Steve chỉcó thể bổ sung thông tin vào dòng tiếp nhận yêu cầu. Nếu tại thời điểm đó cùng có nhiều yêu cầu gửi tới thì yêu cầu của Steve được đưa lên đầu trong nhóm cùng thời điểm. Nếu có nhiều thời điểm cùng cho thời gian chờ đợi nhỏ nhất như nhau thì Steve chọn thời điểm muộn nhất. Biên bản hệ thống cho Steve biết ở dòng xếp hàng đang xử lý có ~x~ người chờ từ dòng xếp hàng cũ chuyển sang, có ~n~ thời điểm có người kết thúc bàn vào xếp hàng chờ bàn mới và tại thời điểm ~t_i~ có ~a_i~ người cùng vào xếp hàng ~(i = 1 \div n)~.
Hãy đưa ra thời điểm Steve chèn yêu cầu của mình và thời gian chờ đợi yêu cầu được đáp ứng.
Dữ liệu vào:
Dòng đầu tiên chứa ~3~ số nguyên ~x, n~ và ~c~ ~(0 \leq x \leq 1000, 1 \leq c \leq 10^4, 0 \leq n \leq c)~, Dòng thứ ~i~ trong ~n~ dòng sau chứa ~2~ số nguyên ~t_i~ và ~a_i~ ~(1 \leq t_{i-1}( < t_i \leq c, 1 \leq a_i \leq 1000)~.
Kết quả ra:
Một dòng gồm ~2~ số nguyên – thời điểm chèn yêu cầu và thời gian chờ đợi.
Sample Input
3 2 5
2 1
3 10
Sample Output
3 1
Nguồn: Thầy Nguyễn Thanh Tùng
Comments