Leveling Ground

Memory limit: 64 MB

Byteasar has decided to build a house. He has chosen a very narrow valley as its location. Before Byteasar starts the actual construction work, he has to level the ground first. He has two excavators at his disposal: the first one can either increase or decrease the ground level of any connected area in the valley by exactly meters; the other can do the same, i.e., either increase or decrease the ground level of any connected area in the valley, but by exactly meters. Notice that neither before such an operation nor after it needs the ground in the affected area be actually leveled.

Given a map of the area, determine the minimum number of operations required to level the ground in the whole valley, i.e., to make the ground level everywhere equal 0. While the operations are performed, the ground level at any point in the valley can have arbitrary value; in particular, it may be negative.

Input

In the first line of the standard input there are three integers, , , (, ), separated by single spaces. The number denotes the valley's length in meters. The second line contains integers, , separated by single spaces. These numbers, all with absolute value no larger than , represent the initial ground level in meters of successive one meter long slices of the valley.

In tests worth 30% of the points the following conditions hold in addition: and .

In tests worth 60% of the points the following conditions hold in addition: and .

In tests worth 90% of the points the condition holds in addition.

Output

In the first and only line of the standard output your program should print a single integer: the minimum number of operations required to level the ground in the whole valley, or if leveling the whole valley with given excavators is impossible.

Example

For the input data:

5 2 3
1 2 1 1 -1

the correct result is:

5

Explanation of the example: One possible solution for the exemplary input is:

• increase the ground level of the first two meters of the valley by meters,
• decrease the ground level of the first two meters of the valley by meters,
• increase the ground level of the last four meters of the valley by meters,
• increase the ground level of the last meter of the valley by meters,
• decrease the ground level of the last four meters of the valley by meters.

Task author: Jakub Pachocki.