Mùa đông đã đến. Nguyên mới phát minh ra một thiết bị làm nóng và cậu ấy quyết định đi thử nó ở Bắc Cực. Một trong những cách hữu hiệu nhất đó chính là đi phá băng.

Ban đầu, thiết bị làm nóng của Nguyên có nhiệt độ là \(T\). Có tất cả \(n\) tảng băng, tảng băng thứ \(i\) có nhiệt độ là \(t_{i}\). Thiết bị làm nóng cần có nhiệt độ lớn hơn hoặc bằng giá trị tuyệt đối của \(t_{i}\) để phá băng. Phá một tảng băng thỏa mãn điều kiện cần \(1\) giây. Khi phá được tảng băng đó, thiết bị làm nóng của Nguyên sẽ hấp thu hơi nước phát ra và nhận được thêm một lượng nhiệt độ bằng \(p_{i}\). Ngoài ra, Nguyên cũng có thể cắm điện và thiết bị làm nóng sẽ nhận một giá trị là \(k\) đơn vị nhiệt độ mỗi giây.

Tóm lại, có hai cách để Nguyên gia tăng nhiệt độ cho thiết bị làm nóng trong \(1\) giây:

• Phá một tảng băng (thỏa mãn điều kiện) và nhận \(p_{i}\) đơn vị nhiệt độ.
• Cắm điện và nhận \(k\) đơn vị nhiệt độ.

Yêu cầu: Tính thời gian ngắn nhất để Nguyên phá được hết tất cả \(n\) tảng băng?

Input

• Dòng thứ nhất chứa ba số nguyên dương \(n,T,k\) (\(n \le 10^3, T \le 10^9, k \le 10^9\)).
• \(n\) dòng tiếp theo, dòng thứ \(n+1\) chứa hai số nguyên \(t_{i}\) và \(p_{i}\) (\(-10^9 \le t_{i} \le -1, 0 \le p_{i} \le 10^9\)).

Output

• Một số nguyên duy nhất là thời gian ngắn nhất để Nguyên phá được hết \(n\) tảng băng.

Example

1 15 20
-35 1

2