Farmer John đã quyết định thực hiện một chuyến nghỉ dưỡng xuyên quốc gia. Tuy nhiên, vì không muốn những cô bò cảm thấy bị bỏ lại, ông đã quyết định thuê một chiếc xe tải lớn và đưa cả đàn bò đi cùng!

Chiếc xe tải có một bình nhiên liệu lớn chứa được tối đa \(G\) đơn vị nhiên liệu (\(1 \le G \le 1\,000\,000\)). Không may, xe tiêu thụ nhiên liệu rất tốn: cứ đi một đơn vị khoảng cách thì tiêu thụ một đơn vị nhiên liệu, và FJ phải đi tổng cộng \(D\) đơn vị khoảng cách trên hành trình của mình (\(1 \le D \le 1\,000\,000\,000\)).

Vì biết rằng có lẽ sẽ phải dừng lại đổ đầy bình vài lần trong chuyến đi, FJ lập danh sách tất cả \(N\) trạm nhiên liệu dọc đường (\(1 \le N \le 50\,000\)). Với mỗi trạm \(i\), ông ghi lại khoảng cách \(X_i\) từ điểm đầu hành trình đến trạm (\(0 \le X_i \le D\)), cũng như giá \(Y_i\) cho mỗi đơn vị nhiên liệu mà trạm bán (\(1 \le Y_i \le 1\,000\,000\)).

Cho các thông tin này và biết rằng FJ bắt đầu hành trình với đúng \(B\) đơn vị nhiên liệu (\(0 \le B \le D\)), hãy xác định số tiền ít nhất FJ cần trả cho nhiên liệu để đến đích. Nếu ông không thể đến đích, hãy in ra -1. Lưu ý rằng đáp án của bài toán này có thể không vừa trong một số nguyên 32 bit tiêu chuẩn.

Dữ liệu vào

• Dòng 1 chứa bốn số nguyên \(N\), \(G\), \(B\) và \(D\), cách nhau bởi dấu cách.
• Các dòng từ 2 đến \(1+N\): mỗi dòng chứa hai số nguyên \(X_i\) và \(Y_i\) mô tả trạm nhiên liệu \(i\).

Dữ liệu ra

• Dòng 1 chứa chi phí ít nhất FJ phải trả để đến đích, hoặc -1 nếu không có cách khả thi nào để ông đến đích.

Ví dụ

4 10 3 17
2 40
9 15
5 7
10 12

174

Nguồn

USACO 2013 US Open, Silver — Problem 2: Fuel Economy

Tác giả đề: Brian Dean, 2013.