Mountain View#10269

Mountain View

2 секунди

256 мегабайтів

Середня

Козак Вус дуже спортивний хлопчина, тому полюбляє альпінізм. Тому цієї зими він вирішив поїхати в гори (на жаль, він не казав куди саме).

Всього є $n$ окремих гірських вершин, розташованих вздовж прямої, $i$ -та вершина має висоту $a_{i}$ a_i метрів та красоту $b_{i}$ b_i. Козак Вус робить наступним чином: він підіймається на одну з гір, дивиться ліворуч та праворуч, після чого бачить деякі інші гори. Козак Вус може побачити $i$ -ту гору, якщо між горою, де він знаходиться, та $i$ -тою горою немає гір з висотою більше або рівно $a_{i}$ a_i метрів. Також Козак Вус бачить гору, на яку він піднявся.

Козак Вус встановив для себе два параметри: $x$ та $y$ . Якщо він підіймається на $1$ метр, його настрій зменшується на $x$ одиниць, а якщо бачить гору з красотою $t$ , то його настрій збільшується на $t y$ одиниць. Спочатку настрій Козак Вуса дорівнює $0$ .

Знайдіть максимально можливий настрій Козака Вуса після підйому на одну з гір.

Зауважте, що Козаку Вусу потрібно піднятися на яку-небудь гору.

Вхідні дані

Перший рядок містить єдине ціле число $n$ ( $1 \leq n \leq 1 0^{6}$ 1 \leq n \leq 10^6) — кількість гір.

Кожен з наступних $n$ рядків містить по два цілі числа $a_{i}$ a_i та $b_{i}$ b_i ( $1 \leq a_{i}, b_{i} \leq 1000$ 1 \leq a_i, b_i \leq 1000) — висоту та красу $i$ -ї гори.

Останній рядок містить два цілі числа $x$ та $y$ ( $1 \leq x, y \leq 1000$ 1 \leq x, y \leq 1000).

Вихідні дані

Виведіть єдине число — максимально можливий настрій Козака Вуса після підйому на одну з гір.

Приклади

Приклад 1

Приклад 2

Приклад 3