Nhà _minhduc có bán những quả bóng ~~cười~~ bay với đủ loại màu sắc rực rỡ, để trang trí cho lớp nhân ngày Cá tháng Tư, shiba quyết định sẽ đến mua bóng ở đây.

Do nhà _minhduc đang hỏng máy bơm, nên shiba phải tự thổi bóng. Quả bóng thứ \(i\) có giá tiền là \(a_{i}\), shiba cần thổi bóng đến đúng kích thước là \(b_{i}\). shiba chỉ có thể thổi được bóng đến kích thước tối đa là \(m\). Nếu không thổi được một quả bóng, shiba có thể đi thuê bơm, giá tiền thuê bơm cho một quả bóng có kích thước cần thổi lớn hơn kích thước cậu ấy có thể thổi là \(b_{i}-m\). Ban đầu, shiba có số tiền là \(k\).

Yêu cầu: Hỏi Nguyên có thể mua và trang trí được tối đa bao nhiêu quả bóng?

Input

• Dòng thứ nhất chứa ba số nguyên dương \(n,m,k\) (\(n \le 10^5, m \le 10^9, k \le 10^{14}\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a_{i}, b_{i}\) (\(a_{i}, b_{i} \le 10^9\)).

Output

• In ra một số nguyên duy nhất là số quả bóng shiba có thể mua và trang trí.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(b_{i} \le m\).
• Subtask \(2\) (\(60\%\) số điểm): không có ràng buộc gì thêm.

Example

5 10 15
11 22
1 2
1 3
1 4
1 5

4