Cat Noku recently picked up construction working as a hobby. He's currently working with a row of buildings and would like to make it beautiful.
There are n buildings in a row. The height of the i-th building is xi.
Cat Noku can modify the buildings by adding or removing floors to change the heights. It costs him P dollars to increase the height of one building by 1, and M dollars to lower the height of one building by 1. Note that the heights of all the buildlings must remain integers (i.e. Cat Noku cannot choose to raise the height of a building by 0.5).
At the end of the day Cat Noku will get a bonus for the number of buildings which are adjacent and have the same height. For each section i, if section i+1 has the same height, Cat Noku will gain a profit of S (of course, it is not possible to get this bonus for the last building in the row). Thus, his net profit can be described by his total profit minus the cost it took him to change the building heights.
Help Cat Noku determine the maximum possible net profit he can gain.
The first line will contain four space separated integers n, S, M, P.
The second line will contain n space separated integers. The i-th integer in this line will be equal to xi.
Print a single integer on its own line, the maximum net profit that Cat Noku can earn.
For all subtasks:
2 ≤ n
1 ≤ xi
1 ≤ S, M, P
Subtask 1 (56 pts):
n ≤ 5
xi ≤ 10
S, M, P ≤ 100
Subtask 2 (32 pts):
n ≤ 50
xi ≤ 100
S, M, P ≤ 1,000
Subtask 3 (12 pts):
n ≤ 2,500
xi ≤ 1,000,000
S, M, P ≤ 1,000,000,000
In this case, we have 5 buildings with heights 1,2,1,5,4. Cat Noku will get a bonus of 4 for adjacent buildings with the same height. It costs 2 dollars to lower the height of a building by 1, and 1 dollar to raise the height by 1.
One optimal solution is to modify the buildings heights to be 1,1,1,5,5. This costs 2+1=3 dollars. Cat Noku gets the bonus 3 times (i.e. the first, second and fourth buildings qualify for the bonus). Thus, his gross profit is 3*4=12. His net profit is 12-3=9 in this case.