e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Ukrainian Olympiad in Informatics, II Stage, II Round

J. Mountain View

Козак Вус дуже спортивний хлопчина, тому полюбляє альпінізм. Тому цієї зими він вирішив поїхати в гори (на жаль, він не казав куди саме). Всього є $n$ окремих гірських вершин, розташованих вздовж прямої, $i$-та вершина має висоту $a_i$ метрів та красоту $b_i$. Козак Вус робить наступним чином: він підіймається на одну з гір, дивиться ліворуч та праворуч, після чого бачить деякі інші гори. Козак Вус може побачити $i$-ту гору, якщо між горою, де він знаходиться, та $i$-тою горою немає гір з висотою \textbf{більше або рівно} $a_i$ метрів. Також Козак Вус бачить гору, на яку він піднявся. Козак Вус встановив для себе два параметри: $x$ та $y$. Якщо він підіймається на $1$ метр, його настрій зменшується на $x$ одиниць, а якщо бачить гору з красотою $t$, то його настрій збільшується на $ty$ одиниць. Спочатку настрій Козак Вуса дорівнює $0$. Знайдіть максимально можливий настрій Козака Вуса після підйому на одну з гір. Зауважте, що Козаку Вусу \textbf{потрібно} піднятися на яку-небудь гору. \InputFile Перший рядок містить єдине ціле число $n$ ($1 \leq n \leq 10^6$)~--- кількість гір. Кожен з наступних $n$ рядків містить по два цілі числа $a_i$ та $b_i$ ($1 \leq a_i, b_i \leq 1000$)~--- висоту та красу $i$-ї гори. Останній рядок містить два цілі числа $x$ та $y$ ($1 \leq x, y \leq 1000$). \OutputFile Виведіть єдине число --- максимально можливий настрій Козака Вуса після підйому на одну з гір.
Time limit 2 seconds
Memory limit 256 MiB
Input example #1
6
5 3
1 5
4 5
3 2
3 2
5 1
1 2
Output example #1
28
Input example #2
1
5 5
1 2
Output example #2
5
Input example #3
3
1000 1
1000 1
1000 1
1000 1
Output example #3
-999997
Author Maksym Oboznyi
Source Ukrainian Olympiad in Informatics 2021, II Stage