eolymp
bolt
Try our new interface for solving problems
Problems

Mountain View

Mountain View

Kozak Vus is a very athletic boy, so he likes mountaineering. Therefore, this winter he decided to go to the mountains (unfortunately, he did not say where). There are a total of $n$ separate mountain peaks located along a straight line, the $i$th peak has a height of $a_i$ meters and a beauty of $b_i$. Cossack Vus does the following: he climbs one of the mountains, looks left and right, after which he sees some other mountains. Cossack Vus can see the $i$th mountain if there are no mountains \textbf{greater than or equal to} $a_i$ meters high between the mountain where he is and the $i$th mountain. Cossack Vus also sees the mountain he climbed. Kozak Vus set two parameters for himself: $x$ and $y$. If he climbs $1$ meter, his mood decreases by $x$ units, and if he sees a mountain with $t$ beauty, then his mood increases by $ty$ units. Initially, the mood of Cossack Mustache is $0$. Find the maximum possible mood of Cossack Mustache after climbing one of the mountains. Note that Cossack Mustache \textbf{needs} to climb some mountain. \InputFile The first line contains a single integer $n$ ($1 \leq n \leq 10^6$)~--- the number of mountains. Each of the following $n$ lines contains two integers $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq 1000$)~--- the height and beauty of the $i$ mountain. The last line contains two integers $x$ and $y$ ($1 \leq x, y \leq 1000$). \OutputFile Derive a single number --- the maximum possible mood of Cossack Mustache after climbing one of the mountains.
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