Soste per riposare#10408
L'agricoltore John e la sua allenatrice personale Bessie stanno scalando il monte Vancouver. Per i loro scopi (e anche per i vostri), la montagna può essere rappresentata come un lungo sentiero rettilineo di lunghezza l~(1 \le l \le 10^6) metri. L'agricoltore John percorrerà il sentiero a velocità costante pari a r_F~(1 \le r_F \le 10^6) secondi per metro. Poiché sta allenando la resistenza, non farà soste per riposare lungo il percorso.
A Bessie, invece, è permesso fare soste per riposare, dove può trovare dell'erba deliziosa. Naturalmente, non può fermarsi ovunque! Lungo il sentiero si trovano n~(1 \le n \le 10^5) luoghi di sosta; l'-esimo di essi si trova a distanza x_i~(0 < x_i < l) metri dall'inizio del sentiero e ha una bontà c_i~(1 \le c_i \le 10^6). Se Bessie riposa nel luogo per secondi, ottiene c_i \cdot t unità di bontà.
Al di fuori dei luoghi di sosta, Bessie cammina a velocità costante pari a r_B~(1 \le r_B \le 10^6) secondi per metro. Poiché Bessie è giovane e in buona forma, r_B è strettamente minore di r_F.
Bessie vuole mangiare quanta più erba deliziosa possibile. Tuttavia, è preoccupata per l'agricoltore John: pensa che se in qualsiasi momento dell'escursione si trovasse dietro di lui sul sentiero, egli potrebbe perdere completamente la motivazione a continuare il cammino!
Aiutate Bessie a trovare la quantità massima totale di unità di bontà che può ottenere, a condizione che l'agricoltore John percorra l'intero tragitto.
Nella prima riga sono forniti quattro numeri interi l, n, r_F e r_B. Le righe successive descrivono i luoghi di sosta: la (i + 1)-esima riga contiene due numeri interi x_i e c_i — la posizione dell'-esimo luogo di sosta e la bontà dell'erba in esso.
È garantito che r_F > r_B e 0 < x_1 < \ldots < x_n < l. Si noti che r_F e r_B sono espressi in secondi per metro!
Stampate un singolo numero intero — la quantità massima totale di unità di bontà che Bessie può ottenere.
Esempio 1
In questo esempio conviene a Bessie fermarsi per secondi nel luogo di sosta con coordinata x = 7 (ottenendo unità di bontà), e poi per un altro secondo nel luogo di sosta con coordinata x = 8 (ottenendo un'ulteriore unità di bontà) — per un totale di unità di bontà.