P3543 [POI 2012] WYR-Leveling Ground

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.

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.

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.