Bác nông dân John và huấn luyện viên riêng của ông, Bessie, đang leo núi Vancowver. Đối với mục đích của họ (và của bạn), ngọn núi có thể được biểu diễn bằng một đường mòn thẳng dài \(L\) mét (\(1 \leq L \leq 10^6\)). Bác nông dân John sẽ đi trên đường mòn với tốc độ không đổi \(r_F\) giây trên mỗi mét (\(1 \leq r_F \leq 10^6\)). Vì đang rèn luyện sức bền, ông sẽ không dừng nghỉ ở bất kỳ trạm nào dọc đường.

Tuy nhiên, Bessie được phép dừng tại các trạm nghỉ, nơi cô có thể tìm thấy một ít cỏ ngon. Dĩ nhiên, cô không thể dừng ở bất cứ đâu! Có \(N\) trạm nghỉ dọc theo đường mòn (\(1 \leq N \leq 10^5\)); trạm thứ \(i\) cách điểm đầu đường mòn \(x_i\) mét (\(0 < x_i < L\)) và có độ ngon \(c_i\) (\(1 \leq c_i \leq 10^6\)). Nếu Bessie nghỉ tại trạm \(i\) trong \(t\) giây, cô nhận được \(c_i \cdot t\) đơn vị độ ngon.

Khi không ở một trạm nghỉ, Bessie sẽ đi bộ với tốc độ cố định \(r_B\) giây trên mỗi mét (\(1 \leq r_B \leq 10^6\)). Vì Bessie còn trẻ và khỏe mạnh nên \(r_B\) nhỏ hơn \(r_F\) một cách nghiêm ngặt.

Bessie muốn ăn được nhiều cỏ ngon nhất có thể. Nhưng cô lo cho bác nông dân John; cô nghĩ rằng nếu tại bất kỳ thời điểm nào trong chuyến đi, cô ở phía sau bác nông dân John trên đường mòn thì ông có thể mất hết động lực để tiếp tục!

Hãy giúp Bessie tìm tổng số đơn vị độ ngon lớn nhất cô có thể nhận được, đồng thời bảo đảm rằng bác nông dân John hoàn thành chuyến đi.

Dữ liệu vào

Dòng đầu tiên chứa bốn số nguyên \(L\), \(N\), \(r_F\) và \(r_B\). \(N\) dòng tiếp theo mô tả các trạm nghỉ. Với mỗi \(i\) từ \(1\) đến \(N\), dòng thứ \(i+1\) chứa hai số nguyên \(x_i\) và \(c_i\), mô tả vị trí của trạm nghỉ thứ \(i\) và độ ngon của cỏ tại đó.

Bảo đảm rằng \(r_F > r_B\) và \(0 < x_1 < \dots < x_N < L\).

Lưu ý rằng \(r_F\) và \(r_B\) được cho theo đơn vị giây trên mỗi mét!

Dữ liệu ra

In ra một số nguyên duy nhất: tổng số đơn vị độ ngon lớn nhất Bessie có thể nhận được.

Ví dụ

10 2 4 3
7 2
8 1

15

Nguồn

USACO 2018 February Contest, Silver — Rest Stops

Tác giả bài toán: Dhruv Rohatgi.