Winter Is Coming
Contest: Codeforces Round 387 (Div. 2)
Difficulty rating: 1800
Tags: dp, greedy, sortings

The winter in Berland lasts n days. For each day we know the forecast for the average air temperature that day.

Vasya has a new set of winter tires which allows him to drive safely no more than k days at any average air temperature. After k days of using it (regardless of the temperature of these days) the set of winter tires wears down and cannot be used more. It is not necessary that these k days form a continuous segment of days.

Before the first winter day Vasya still uses summer tires. It is possible to drive safely on summer tires any number of days when the average air temperature is non-negative. It is impossible to drive on summer tires at days when the average air temperature is negative.

Vasya can change summer tires to winter tires and vice versa at the beginning of any day.

Find the minimum number of times Vasya needs to change summer tires to winter tires and vice versa to drive safely during the winter. At the end of the winter the car can be with any set of tires.

Input format:
The first line contains two positive integers n and k (1 ≤ n ≤ 2·105, 0 ≤ k ≤ n) — the number of winter days and the number of days winter tires can be used. It is allowed to drive on winter tires at any temperature, but no more than k days in total.

The second line contains a sequence of n integers t1, t2, ..., tn ( - 20 ≤ ti ≤ 20) — the average air temperature in the i-th winter day.

Output format:
Print the minimum number of times Vasya has to change summer tires to winter tires and vice versa to drive safely during all winter. If it is impossible, print -1.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example before the first winter day Vasya should change summer tires to winter tires, use it for three days, and then change winter tires to summer tires because he can drive safely with the winter tires for just three days. Thus, the total number of tires' changes equals two.

In the second example before the first winter day Vasya should change summer tires to winter tires, and then after the first winter day change winter tires to summer tires. After the second day it is necessary to change summer tires to winter tires again, and after the third day it is necessary to change winter tires to summer tires. Thus, the total number of tires' changes equals four.

Example input:
4 3
-5 20 -3 0

Example output:
2

Example input:
4 2
-5 20 -3 0

Example output:
4

Editorial:
At first let's process the case when there is no solution — when the number of days with negative temperature cnt more than k. Now we need to subtract from k the number of days cnt.
If we will use winter rubber only in days with negative temperature we will get the maximum value of answer: it is the number of segments where all days have negative temperature multiply by 2.
Between the segments with negative temperatures there are segments which we ride on the summer rubber. Let's put in set the lengths of this segments (not include the segments with first and last days if thеy have non-negative temperatures, this cases we need to process separately from the main solution).
After that we need to delete from the set smallest lengths of segments one by one, decrease k on this value and decrease answer on 2. We can make it until k >  = 0 and the set is not empty.
Now we only need to check if we can ride on winter rubber the last segment of days with non-negative temperature. If it is possible we need decrease the answer on 1, in the other case the answer remains unchanged.