Зупинки для відпочинку#10408

Зупинки для відпочинку

1 секунда

128 мегабайтів

Середня

Фермер Джон та його особистий тренер Бессі піднімаються на гору Ванкувер. Для їхньої мети (і Вашої також) гору можна уявити як довгу пряму стежку довжиною $l (1 \leq l \leq 1 0^{6})$ l~(1 \le l \le 10^6) метрів. Фермер Джон йтиме стежкою зі сталою швидкістю $r_{F} (1 \leq r_{F} \leq 1 0^{6})$ r_F~(1 \le r_F \le 10^6) секунди на метр. Оскільки він тренує витривалість, він не робитиме зупинок для відпочинку по дорозі.

Бессі ж дозволено робити зупинки для відпочинку, де вона може знайти трохи смачної трави. Звичайно ж, зупинятися де завгодно вона не може! Уздовж стежки розташовано $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) місць для відпочинку; $i$ -те з них знаходиться на відстані $x_{i} (0 < x_{i} < l)$ x_i~(0 < x_i < l) метрів від початку стежки і має смачність $c_{i} (1 \leq c_{i} \leq 1 0^{6})$ c_i~(1 \le c_i \le 10^6). Якщо Бессі відпочиває у місці $i$ протягом $t$ секунд, вона отримує $c_{i} \cdot t$ c_i \cdot t одиниць смачності.

Поза місцями для відпочинку Бессі йде зі сталою швидкістю $r_{B} (1 \leq r_{B} \leq 1 0^{6})$ r_B~(1 \le r_B \le 10^6) секунд на метр. Оскільки Бессі молода і перебуває у гарній формі, $r_{B}$ r_B строго менше за $r_{F}$ r_F.

Бессі хоче з'їсти якомога більше смачної трави. Проте вона турбується про фермера Джона: вона вважає, що якщо в якийсь момент походу вона опиниться позаду нього на стежці, він може повністю втратити мотивацію продовжувати шлях!

Допоможіть Бессі знайти максимальну сумарну кількість одиниць смачності, яку вона може отримати, за умови, що фермер Джон пройде весь маршрут.

Вхідні дані

У першому рядку задано чотири цілих числа $l, n, r_{F}$ l, n, r_F та $r_{B}$ r_B. Наступні $n$ рядків описують місця для відпочинку: $(i + 1)$ (i + 1)-й рядок містить два цілих числа $x_{i}$ x_i та $c_{i}$ c_i — позицію $i$ -го місця для відпочинку та смачність трави в ньому.

Гарантується, що $r_{F} > r_{B}$ r_F > r_B та $0 < x_{1} < \dots < x_{n} < l$ 0 < x_1 < \ldots < x_n < l. Зверніть увагу, що $r_{F}$ r_F та $r_{B}$ r_B задані в секундах на метр!

Вихідні дані

Виведіть одне ціле число — максимальну сумарну кількість одиниць смачності, яку може отримати Бессі.

Приклади

Приклад 1

Примітка

У цьому прикладі Бессі вигідно зупинитися на $7$ секунд у місці для відпочинку з координатою $x = 7$ x = 7 (отримавши $14$ одиниць смачності), а потім ще на $1$ секунду у місці для відпочинку з координатою $x = 8$ x = 8 (отримавши ще $1$ одиницю смачності) — загалом $15$ одиниць смачності.