Фермер Джон и его персональный тренер Беси подымаются на гору Ванкувера.
Эта гора может быть представлена как тропинка длиной \(L\) метров
(\(1 \leq L \leq 10^6\)). ФД двигается по ней со скоростью \(r_F\) секунд в метр
(\(1 \leq r_F \leq 10^6\)). Он не делает остановок во время движения.
Беси, однако разрешено делать остановки для отдыха и поедания травы.
Но она может их делать не везде. Имеется \(N\) мест для остановок на тропинке
(\(1 \leq N \leq 10^5\)); \(i\)-ая остановка находится на \(x_i\) метров от начала
тропинки (\(0 < x_i < L\)), а трава на ней имеет вкусность \(c_i\)
(\(1 \leq c_i \leq 10^6\)). Если Беси остановится в месте \(i\) на \(t\) секунд,
она получит \(c_i \cdot t\) вкусности травы.
Беси двигается со скоростью \(r_B\) секунд за метр (\(1 \leq r_B \leq 10^6\)).
Поскольку Беси моложе, \(r_B\) строго меньше \(r_F\).
Беси хочет максимизировать потребление вкусной травы. Но она беспокоится о ФД.
Она думает, что если окажется позади ФД, у него пропадёт мотивация продолжать
движение.
Помогите Беси найти максимальное суммарное значение съеденной вкусной травы
которое она может получить, в уверенности, что ФД завершит подъём.
ФОРМАТ ВВОДА (файл reststops.in):
Первая строка ввода содержит четыре целых числа:
\(L\),
\(N\),
\(r_F\),
\(r_B\).
Следующие
\(N\) строк описывают остановки. Для каждого
\(i\) от
\(1\) до
\(N\),
\(i+1\)-ая строка содержит два целых числа
\(x_i\) и
\(c_i\), описывающих позицию
\(i\)-ой остановки и вкусность травы здесь.
Гарантируется, что \(r_F > r_B\), и \(0 < x_1 < \dots < x_N < L \).
Заметим, что \(r_F\) и \(r_B\) задаются в секундах на метр!
ФОРМАТ ВЫВОДА (файл reststops.out):
Одно целое число: максимальное количество единиц вкусности, которое Беси может
получить.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 2 4 3
7 2
8 1
|
15
|