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.

just in one line.
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.