Minz được giao chăm sóc một khu vườn gồm ~N~ cây trong ~D~ ngày.

Ở ngày ~0~, cây thứ ~i~ có chiều cao ~H_i~. Trong mỗi ngày, các sự kiện diễn ra theo thứ tự:

1. Ban ngày, Minz được chọn tối đa một cây để cắt. Chiều cao của cây được chọn giảm ~P~; nếu chiều cao hiện tại nhỏ hơn ~P~ thì cây được cắt về ~0~. Minz cũng có thể không cắt cây nào;
2. Ban đêm, cây thứ ~i~ mọc thêm ~A_i~.

Gọi ~M~ là chiều cao lớn nhất của một cây tại bất kỳ thời điểm nào, tính từ ngày ~0~ đến hết ngày ~D~.

Yêu cầu

Hãy lập lịch cắt cây sao cho ~M~ nhỏ nhất có thể.

Input

Từ tệp văn bản TRIM.INP:

• Dòng đầu tiên chứa ba số nguyên ~N, D, P~ ~(1 \le N, D \le 10^5; 1 \le P \le 10^9)~;
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~H_i, A_i~ ~(0 \le H_i, A_i \le 10^9)~.

Output

Ghi vào tệp văn bản TRIM.OUT:

• Một số nguyên duy nhất là ~M_{\min}~, giá trị nhỏ nhất có thể của chiều cao cực đại trong toàn bộ quá trình.

Ràng buộc

• Subtask 1 (20% số điểm): ~N = 1~;
• Subtask 2 (20% số điểm): ~N, D \le 1000~ và ~H_i, A_i, P \le 1000~;
• Subtask 3 (20% số điểm): ~H_i, A_i \le 5000~ và ~P = 10^9~;
• Subtask 4 (40% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input

2 2 10
5 5
8 2

Output

10

Giải thích

Ở ngày ~0~, hai cây cao lần lượt ~5~ và ~8~.

• Ngày ~1~, Minz cắt cây thứ hai về ~0~; sau khi sinh trưởng, hai cây cao ~10~ và ~2~;
• Ngày ~2~, Minz cắt cây thứ nhất về ~0~; sau khi sinh trưởng, hai cây cao ~5~ và ~4~.

Chiều cao lớn nhất từng xuất hiện là ~10~, và không có lịch cắt nào đạt kết quả nhỏ hơn.