# Uncomment

In a, programmers' day,
Comment, all the lines I may.
N lines, there should be.
Commented A_i as I've been.
Select a region,
Toggle its comment.
Cost of all,
is (R-L+1)*A+B for all.
just in one line.
and give it C bears.
Ah! The Mighty You!
Why are you standing still!
In the cost of all the days,
I shall let them all on the bay!


Formally, you are given N integers. The i-th integer is A_i
You can do the following operation:

• "toggle L R" at the cost of X(R-L+1)+Y

• "comment X" at the cost of Z

"toggle" operation will decrease all numbers from L to R by 1 if there is no 0 in the range L to R. Otherwise, it will increase all numbers from L to R by 1. For example, doing toggle on "1 2 3" will become "0 1 2" and on "1 0 2 4" will become "2 1 3 5"
"comment" operation will increase number X by 1.
What's the minimal cost to make all numbers 0?

# Examples

Input:
A={1,0,2,4}
X=0,Y=2,Z=0
Output:
8
Explain:
Add all numbers to 4, then decrease them all.