Dincəlmə dayanacaqları
Fermer Con və onun şəxsi məşqçisi Bessi Vankovver dağına qalxırlar. Bu dağ l (1 ≤ l ≤ 10^6) metr uzunluğunda bir cığır kimi təsvir edilə bilər. Fermer Con cığır boyunca sabit r[F] (1 ≤ r[F] ≤ 10^6) saniyə/metr sürətlə hərəkət edir. O, dözümlülüyü üzərində işlədiyi üçün yolda istirahət üçün dayanmayacaq.
Bessi isə istirahət etmək və ot yemək üçün dayanmağa icazə verilir. Əlbəttə ki, o, hər yerdə dayana bilməz! Marşrutda n (1 ≤ n ≤ 10^5) istirahət dayanacağı var; i-ci dayanacaq cığırın başlanğıcından x[i] (0 < x[i] < l) metr məsafədə yerləşir və c[i] (1 ≤ c[i] ≤ 10^6) dad dəyərinə malikdir. Əgər Bessi i-ci dayanacaqda t saniyə istirahət edərsə, o, c[i] * t dad vahidi əldə edəcək.
Əgər istirahət dayanacağı yoxdursa, Bessi sabit r[B] (1 ≤ r[B] ≤ 10^6) saniyə/metr sürətlə piyada hərəkət edəcək. Bessi gənc və sağlam olduğundan, r[B] r[F]-dən ciddi şəkildə kiçikdir.
Bessi dadlı ot istehlakını maksimuma çatdırmaq istəyir. Lakin o, fermer Con haqqında narahatdır; o düşünür ki, əgər yürüşün hər hansı bir anında Conun arxasında qalsa, Con hər hansı bir motivasiyanı itirə bilər.
Bessiyə əldə edə biləcəyi maksimum dad vahidlərini tapmağa kömək edin və əmin olun ki, fermer Con yürüşü tamamlayacaq.
Giriş Məlumatları
Birinci sətir dörd tam ədədi ehtiva edir: l, n, r[F] və r[B]. Növbəti n sətir istirahət dayanacaqlarını təsvir edir. 1 və n arasında hər bir i üçün, (i + 1)-ci sətir x[i] və c[i] tam ədədlərini ehtiva edir, i-ci istirahət dayanacağının yerini və oradakı otun dad keyfiyyətlərini təsvir edir.
Zəmanət verilir ki, r[F] > r[B] və 0 < x[1] < ... < x[n] < l. Qeyd edək ki, r[F] və r[B] metr başına saniyə ilə verilir.
Çıxış Məlumatları
Bir tam ədəd çıxarın: Bessinin əldə edə biləcəyi maksimum dad vahidlərinin sayı.
Nümunə
Bu nümunədə Bessi üçün x = 7 istirahət dayanacağında 7 saniyə dayanmaq (14 dad vahidi əldə edərək) və sonra x = 8 istirahət dayanacağında daha 1 saniyə dayanmaq (1 daha dad vahidi əldə edərək, cəmi 15 dad vahidi) optimaldır.