Dincəlmə yerləri#10408

Dincəlmə yerləri

1 saniyə

128 meqabayt

Orta

Fermer Con və onun şəxsi məşqçisi Bessi Vankuver dağına qalxırlar. Sizin (və onların) məqsədləriniz üçün dağı uzunluğu $l (1 \leq l \leq 1 0^{6})$ l~(1 \le l \le 10^6) metr olan uzun düz bir cığır kimi təsəvvür etmək olar. Fermer Con cığır boyunca sabit sürətlə, yəni $r_{F} (1 \leq r_{F} \leq 1 0^{6})$ r_F~(1 \le r_F \le 10^6) saniyə/metr sürətlə gedəcək. Dözümlülüyünü artırdığı üçün, yolda dayanıb dincəlməyəcək.

Bessiyə isə dincəlmək üçün dayanmağa icazə verilir, harada ki, o, dadlı ot tapa bilər. Əlbəttə ki, o, istənilən yerdə dayana bilməz! Cığır boyunca $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) dincəlmə yeri yerləşir; onların $i$ -cisi cığırın başlanğıcından $x_{i} (0 < x_{i} < l)$ x_i~(0 < x_i < l) metr məsafədə yerləşir və $c_{i} (1 \leq c_{i} \leq 1 0^{6})$ c_i~(1 \le c_i \le 10^6) dadlılıq dərəcəsinə malikdir. Əgər Bessi $i$ -ci yerdə $t$ saniyə dincəlirsə, o, $c_{i} \cdot t$ c_i \cdot t vahid dadlılıq əldə edir.

Dincəlmə yerlərindən kənarda Bessi sabit sürətlə, yəni $r_{B} (1 \leq r_{B} \leq 1 0^{6})$ r_B~(1 \le r_B \le 10^6) saniyə/metr sürətlə gedir. Bessi gənc və yaxşı formada olduğu üçün, $r_{B}$ r_B dəqiq olaraq $r_{F}$ r_F-dən kiçikdir.

Bessi mümkün qədər çox dadlı ot yemək istəyir. Lakin o, Fermer Con haqqında narahatdır: o düşünür ki, əgər gəzintinin hər hansı anında cığırda ondan geri qalarsa, bu, Fermer Conun yolu davam etdirmək həvəsini tamamilə itirməsinə səbəb ola bilər!

Bessiyə, Fermer Conun bütün marşrutu keçəcəyi şərti ilə, əldə edə biləcəyi maksimum ümumi dadlılıq vahidlərinin sayını tapmağa kömək edin.

Giriş

Birinci sətirdə dörd tam ədəd verilir: $l, n, r_{F}$ l, n, r_F və $r_{B}$ r_B. Növbəti $n$ sətir dincəlmə yerlərini təsvir edir: $(i + 1)$ (i + 1)-ci sətirdə iki tam ədəd — $x_{i}$ x_i və $c_{i}$ c_i — $i$ -ci dincəlmə yerinin mövqeyi və orada olan otun dadlılığı verilir.

Təminat verilir ki, $r_{F} > r_{B}$ r_F > r_B və $0 < x_{1} < \dots < x_{n} < l$ 0 < x_1 < \ldots < x_n < l. Diqqət edin ki, $r_{F}$ r_F və $r_{B}$ r_B saniyə/metr vahidində verilib!

Çıxış

Bessinin əldə edə biləcəyi maksimum ümumi dadlılıq vahidlərinin sayını bildirən bir tam ədəd çıxarın.

Nümunələr

Nümunə 1

Qeyd

Bu nümunədə Bessi üçün $x = 7$ x = 7 koordinatlı dincəlmə yerində $7$ saniyə dayanmaq ( $14$ vahid dadlılıq əldə etmək), sonra isə $x = 8$ x = 8 koordinatlı dincəlmə yerində daha $1$ saniyə dayanmaq (daha $1$ vahid dadlılıq əldə etmək) sərfəlidir — cəmi $15$ vahid dadlılıq.