思考题 in poems

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.
Or add a comment,
just in one line.
Move your fingers,
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.

Constriants

Subtask1(10%):X=0
Subtask2(10%):Y=0
Subtask3(10%):Z=0
Subtask4(10%):N=1
Subtask5(10%):A_i=0 for all I
Subtask6(10%):N<=1000
Subtask7(40%):N<=100000,A,X,Y,Z<=1e9

Orange Boy AKed the contest so he solved this one.