Dinlenme Molaları#10408

Dinlenme Molaları

1 saniye

128 megabayt

Orta

Çiftçi John ve kişisel antrenörü Bessie, Vancouver Dağı'na tırmanıyorlar. Onların amaçları doğrultusunda (ve sizin de amacınız doğrultusunda), dağ, uzunluğu $l (1 \leq l \leq 1 0^{6})$ l~(1 \le l \le 10^6) metre olan uzun düz bir patika olarak düşünülebilir. Çiftçi John, patika boyunca sabit bir hızla, metre başına $r_{F} (1 \leq r_{F} \leq 1 0^{6})$ r_F~(1 \le r_F \le 10^6) saniye hızında yürüyecektir. Dayanıklılığını geliştirdiği için, yol boyunca dinlenmek için hiç durmayacaktır.

Bessie ise, lezzetli biraz ot bulabileceği yerlerde dinlenmek için durabilir. Elbette, istediği her yerde duramaz! Patika boyunca $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) dinlenme yeri bulunmaktadır; bunlardan $i$ -inci olanı, patikanın başlangıcından $x_{i} (0 < x_{i} < l)$ x_i~(0 < x_i < l) metre uzaklıkta bulunur ve $c_{i} (1 \leq c_{i} \leq 1 0^{6})$ c_i~(1 \le c_i \le 10^6) lezzet değerine sahiptir. Eğer Bessie $i$ numaralı yerde $t$ saniye boyunca dinlenirse, $c_{i} \cdot t$ c_i \cdot t birim lezzet elde eder.

Dinlenme yerlerinin dışında, Bessie sabit bir hızla, metre başına $r_{B} (1 \leq r_{B} \leq 1 0^{6})$ r_B~(1 \le r_B \le 10^6) saniye hızında yürür. Bessie genç ve iyi formda olduğu için, $r_{B}$ r_B kesinlikle $r_{F}$ r_F'den küçüktür.

Bessie mümkün olduğunca fazla lezzetli ot yemek istiyor. Ancak Çiftçi John için endişeleniyor: eğer yolculuğun herhangi bir anında patikada ondan geride kalırsa, onun yürüyüşe devam etme motivasyonunu tamamen kaybedebileceğini düşünüyor!

Çiftçi John'un tüm rotayı tamamlayacağı koşulu altında, Bessie'nin elde edebileceği maksimum toplam lezzet birimi sayısını bulmasına yardım edin.

Giriş

İlk satırda dört tam sayı verilir: $l, n, r_{F}$ l, n, r_F ve $r_{B}$ r_B. Sonraki $n$ satır dinlenme yerlerini tanımlar: $(i + 1)$ (i + 1)-inci satır iki tam sayı içerir, $x_{i}$ x_i ve $c_{i}$ c_i — $i$ -inci dinlenme yerinin konumu ve oradaki otun lezzet değeri.

$r_{F} > r_{B}$ r_F > r_B ve $0 < x_{1} < \dots < x_{n} < l$ 0 < x_1 < \ldots < x_n < l olduğu garanti edilir. $r_{F}$ r_F ve $r_{B}$ r_B'nin metre başına saniye cinsinden verildiğine dikkat edin!

Çıktı

Bessie'nin elde edebileceği maksimum toplam lezzet birimi sayısını temsil eden tek bir tam sayı yazdırın.

Örnekler

Örnek 1

Not

Bu örnekte, Bessie'nin $x = 7$ x = 7 koordinatındaki dinlenme yerinde $7$ saniye durması (böylece $14$ birim lezzet elde etmesi) ve ardından $x = 8$ x = 8 koordinatındaki dinlenme yerinde $1$ saniye daha durması (böylece $1$ birim daha lezzet elde etmesi) avantajlıdır — toplamda $15$ birim lezzet.