Фермер Джон и его личный тренер Бесси поднимаются на гору Ванковвер. Эта гора может быть представлена как тропинка длиной l (1 ≤ l ≤ 10^6
) метров. Фермер Джон двигается по тропе с постоянной скоростью r[F]
(1 ≤ r[F]
≤ 10^6
) секунд на метр. Поскольку он работает над своей выносливостью, то не будет делать остановок для отдыха на пути.
Бесси, однако, разрешено делать остановки для отдыха и поедания травы. Конечно, она не может остановиться где попало! На маршруте есть n (1 ≤ n ≤ 10^5
) остановок для отдыха; i-я остановка находится в x[i]
(0 < x[i]
< l) метрах от начала тропы и имеет значение вкуса c[i]
(1 ≤ c[i]
≤ 10^6
). Если Бесси отдыхает на остановке i в течение t секунд, то она получит c[i]
* t единиц вкусности.
Если нет остановки для отдыха, Бесси будет двигаться пешком с фиксированной скоростью r[B]
(1 ≤ r[B]
≤ 10^6
) секунд на метр. Поскольку Бесси молода и здорова, r[B]
строго меньше, чем r[F]
.
Бесси хотела бы максимально увеличить потребление вкусной травы. Но она беспокоится о фермере Джоне; она думает, что если в какой-то момент похода она окажется позади фермера Джона, то он может потерять всякую мотивацию продолжать путь.
Помогите Бесси найти максимальное количество единиц вкуса, которое она может получить, и убедитесь, что фермер Джон завершит поход.
Первая строка содержит четыре целых числа: l, n, r[F]
и r[B]
. Следующие n строк описывают остановки для отдыха. Для каждого i между 1 и n, (i + 1)-ая строка содержит два целых числа x[i]
и c[ i]
, описывая положение i-й остановки отдыха и вкусовые качества травы там.
Гарантируется, что r[F]
> r[B]
и 0 < x[1]
< ... < x[n]
< l. Обратите внимание, что r[F]
и r[B]
даны в секундах на метр.
Выведите одно целое число: максимальное количество единиц вкуса, которое может получить Бесси.
В этом примере для Бесси оптимально остановиться на 7 секунд на x = 7 остановке для отдыха (получив 14 единиц вкуса), а затем остановиться еще на 1 секунду на x = 8 остановке для отдыха (получив на 1 больше единиц вкуса, всего 15 единиц вкуса).