思考题 in poems

Uncomment

In a, programmers' day,
Comment, all the lines I may.
{% mathjax %}N{% endmathjax %} lines, there should be.
Commented {% mathjax %}A_i{% endmathjax %} as I've been.

Select a region,
Toggle its comment.
Cost of all,
is {% mathjax %}(R-L+1)*A+B{% endmathjax %} for all.

Or add a comment,
just in one line.
Move your fingers,
and give it {% mathjax %}C{% endmathjax %} 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 integers. The i-th integer is

You can do the following operation:

  • "toggle L R" at the cost of

  • "comment X" at the cost of

"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%):=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.