Hệ thống của công ty SAGA cứ sau ~c~ phút lại mở một phiên giao dịch mới (thời gian trong phiên được tính từ ~0~ đến ~c~ rồi quay lại ~0~). Người chơi nào đã vượt qua hết các bàn hiện có sẽ được đưa vào hàng đợi chờ được cung cấp bàn mới.

Trong quá trình phục vụ, cứ mỗi phút server sẽ gửi bản cập nhật cho đúng 1 người đang chờ trong hàng (nếu hàng không rỗng). Khi người chơi vượt qua một bàn, hệ thống ghi nhận thời điểm kết thúc ~t~ (theo thời gian trong phiên) và đưa người đó vào hàng đợi. Có thể có nhiều người cùng kết thúc tại một thời điểm.

Steve có thể chèn yêu cầu của mình vào dòng tiếp nhận yêu cầu tại một thời điểm ~T~ (số nguyên). Nếu tại thời điểm đó cũng có người chơi khác gửi yêu cầu thì yêu cầu của Steve được xếp lên đầu trong nhóm cùng thời điểm (nhưng vẫn đứng sau tất cả những người đã có trong hàng từ trước).

Biên bản hệ thống cho biết: tại thời điểm ~0~ của phiên hiện tại, hàng đợi đang có sẵn ~x~ người từ phiên cũ chuyển sang. Trong phiên có ~n~ thời điểm ~t_i~ có người kết thúc và tại thời điểm đó có ~a_i~ người cùng vào hàng.

Yêu cầu

Hãy chọn thời điểm chèn ~T~ sao cho thời gian chờ của Steve là nhỏ nhất. Nếu có nhiều thời điểm cho cùng thời gian chờ nhỏ nhất, chọn thời điểm muộn nhất.

Cần in ra:

• ~T~: thời điểm Steve chèn yêu cầu
• ~W~: thời gian chờ (tính bằng số phút) để Steve được server phục vụ

Quy ước mô phỏng trong mỗi phút tại thời điểm nguyên ~t~:

1. Tất cả yêu cầu có thời điểm ~t~ được đưa vào cuối hàng (Steve đứng đầu trong nhóm cùng ~t~ nếu chọn ~T=t~).
2. Nếu hàng không rỗng, server phục vụ 1 người ở đầu hàng ngay tại thời điểm đó.

Dữ liệu

• Dòng 1: ba số nguyên ~x, n, c~ (~0 \le x \le 1000~, ~1 \le c \le 10^4~, ~0 \le n \le c~)
• Trong ~n~ dòng tiếp theo: hai số nguyên ~t_i, a_i~ (~1 \le t_1 < t_2 < \dots < t_n \le c~, ~1 \le a_i \le 1000~)

Kết quả

In ra trên một dòng 2 số nguyên:

• ~T~: thời điểm chèn yêu cầu
• ~W~: thời gian chờ nhỏ nhất tương ứng

Ví dụ

Ví dụ 1

Input

3 2 5
2 1
3 10

Output

3 1

Giải thích

Ví dụ 1

Ban đầu hàng có ~3~ người.

• Trước thời điểm ~2~, server phục vụ được 2 người, còn ~1~ người.
• Ở thời điểm ~2~ có thêm ~1~ người vào, sau đó server phục vụ 1 người nên trước thời điểm ~3~ vẫn còn ~1~ người.
• Nếu Steve chèn ở ~T=3~ thì trước lúc chèn có ~1~ người đứng trước, nên thời gian chờ là ~W=1~. Đây là nhỏ nhất, và giữa các thời điểm cho ~W=1~ thì ~T=3~ là muộn nhất.

Ràng buộc và chấm điểm

Ràng buộc

• ~0 \le x \le 1000~
• ~1 \le c \le 10^4~
• ~0 \le n \le c~
• ~1 \le a_i \le 1000~, ~1 \le t_1 < \dots < t_n \le c~