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-----

The first line contains two positive integers n and k (1 ≤ n ≤ 2·10^5, 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 t_1, t_2, ..., t_{n} ( - 20 ≤ t_{i} ≤ 20) — the average air temperature in the i-th winter day. 


-----Output-----

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.


-----Examples-----
Input
4 3
-5 20 -3 0

Output
2

Input
4 2
-5 20 -3 0

Output
4

Input
10 6
2 -5 1 3 0 0 -4 -3 1 0

Output
3



-----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.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Sorting

Greedy algorithms
Skill types: Dynamic programming

Sorting

Greedy algorithms

Starter code:

Solutions:
def solve():
	(n, k) = list(map(int, input().split()))
	temps = list(map(int, input().split()))
	summer_seqs = []
	winter_seqs = []
	cur_season = 1
	cur_len = 0
	for t in temps:
		if cur_season * t > 0 or (t == 0 and cur_season == 1):
			cur_len += 1
		else:
			if cur_season == 1:
				summer_seqs.append(cur_len)
			else:
				winter_seqs.append(cur_len)
			cur_len = 1
			cur_season = -cur_season
	if cur_season == 1:
		summer_seqs.append(cur_len)
	else:
		winter_seqs.append(cur_len)
	summer_seqs = summer_seqs[1:]
	cur_len = sum(winter_seqs)
	if cur_len > k:
		return -1
	if len(summer_seqs) == 0:
		return 1 if len(winter_seqs) != 0 else 0
	changes = len(summer_seqs) + len(winter_seqs)
	last_sum_seq = None
	if temps[-1] >= 0:
		last_sum_seq = summer_seqs[-1]
		summer_seqs = summer_seqs[:-1]
	summer_seqs = list(sorted(summer_seqs))
	for s in summer_seqs:
		if k - cur_len >= s:
			changes -= 2
			cur_len += s
		else:
			break
	if last_sum_seq is not None:
		if k - cur_len >= last_sum_seq:
			changes -= 1
	return changes

def __starting_point():
	print(solve())
__starting_point()


(n, k) = map(int, input().split())
d = list(map(int, input().split()))
p = []
count = 0
count1 = 0
for i in range(len(d)):
	if d[i] >= 0:
		count += 1
	if d[i] < 0 or i == len(d) - 1:
		p.append(count)
		count = 0
		count1 += 1
if d[len(d) - 1] >= 0:
	count1 -= 1
if count1 == 0:
	print(0)
	return
a = p.pop() if d[len(d) - 1] >= 0 else 0
if len(p) > 0:
	p.reverse()
	p.pop()
	p.sort()
count = k - len(p) - 1 if count1 > 1 else k - count1
if count < 0:
	print(-1)
	return
count1 = 0
for i in range(len(p)):
	if count - p[i] >= 0:
		count1 += 1
		count -= p[i]
	else:
		break
ans = 2 * (len(p) + 1 - count1)
if count - a >= 0:
	ans -= 1
print(ans)


import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n
avl = AvlTree()

class SegmentTree1:

	def __init__(self, data, default='z', func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
(n, k) = map(int, input().split())
l = list(map(int, input().split()))
ans = 0
st = -1
u = 0
if l[0] < 0:
	st = 0
	u += 1
	ans += 1
for i in range(1, n):
	if l[i] < 0 and st == -1:
		st = i
	if l[i] < 0:
		u += 1
	if l[i] < 0 and l[i - 1] >= 0:
		ans += 1
	elif l[i] >= 0 and l[i - 1] < 0:
		ans += 1
e = []
cur = 0
for i in range(st, n):
	if l[i] >= 0:
		cur += 1
	else:
		if cur == 0:
			continue
		e.append(cur)
		cur = 0
e.sort()
r = 0
rel = k - u
if rel < 0:
	print(-1)
	sys.exit()
if sum(e) + cur <= rel:
	print(1)
	sys.exit()
for i in range(len(e)):
	r += e[i]
	if rel < r:
		ans -= 2 * i
		rel = rel - r + e[i]
		break
if rel >= r:
	ans -= 2 * len(e)
	rel -= sum(e)
if cur > 0 and rel >= cur:
	ans -= 1
print(ans)


(n, k) = map(int, input().split())
inF = False
bad = 0
last = None
stretches = [0]
for d in map(lambda x: int(x) >= 0, input().split()):
	last = d
	if d and (not inF):
		continue
	else:
		inF = True
		if d:
			stretches[-1] += 1
		else:
			bad += 1
			if stretches[-1] != 0:
				stretches.append(0)
if bad > k:
	print(-1)
elif bad == 0:
	print(0)
elif n == k:
	print(1)
else:
	k -= bad
	num = 1
	if last:
		num -= 1
	if stretches[-1] == 0:
		del stretches[-1]
	num_ = num
	stretches_ = stretches[:-1]
	k_ = k
	if len(stretches) > 0:
		num += len(stretches) * 2
		last = stretches[-1]
		stretches.sort()
		while len(stretches) > 0 and stretches[0] <= k:
			num -= 2
			k -= stretches[0]
			del stretches[0]
		if not last in stretches:
			num += 1
	if len(stretches_) > 0:
		num_ += (len(stretches_) + 1) * 2
		stretches_.sort()
		while len(stretches_) > 0 and stretches_[0] <= k_:
			num_ -= 2
			k_ -= stretches_[0]
			del stretches_[0]
		print(min(num, num_))
	else:
		print(num)


import heapq
mod = 1000000007
pi = 3.141592653589793
IS = float('inf')
xy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
bs = [(-1, -1), (-1, 1), (1, 1), (1, -1)]

def niten(a, b):
	return abs(a - b) if a >= 0 and b >= 0 else a + abs(b) if a >= 0 else abs(a) + b if b >= 0 else abs(abs(a) - abs(b))

def fib(n):
	return [(seq.append(seq[i - 2] + seq[i - 1]), seq[i - 2])[1] for seq in [[0, 1]] for i in range(2, n)]

def gcd(a, b):
	return a if b == 0 else gcd(b, a % b)

def lcm(a, b):
	return a * b / gcd(a, b)

def eucl(x1, y1, x2, y2):
	return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5

def choco(xa, ya, xb, yb, xc, yc, xd, yd):
	return 1 if abs((yb - ya) * (yd - yc) + (xb - xa) * (xd - xc)) < 1e-10 else 0

def pscl(num, l=[1]):
	for i in range(num):
		l = map(lambda x, y: x + y, [0] + l, l + [0])
	return l
(n, k) = [int(i) for i in input().split()]
l = [int(i) for i in input().split()]
cnt = [i for i in l if i < 0]
m = 0
for (a, i) in enumerate(l):
	if i < 0 and m == 0:
		m = 1
	elif i < 0 and l[a - 1] >= 0:
		m += 1
d = {}
q = []
chk = -1
for i in l:
	if i < 0:
		if chk > 0:
			if chk in d:
				d[chk] += 1
			else:
				d[chk] = 1
				heapq.heappush(q, chk)
		chk = 0
	elif chk >= 0:
		chk += 1
ans = m * 2
k -= len(cnt)
while len(q) and k >= q[0]:
	k -= q[0]
	ans -= 2
	d[q[0]] -= 1
	if d[q[0]] == 0:
		heapq.heappop(q)
if k >= chk and chk > -1:
	ans -= 1
print(ans if ans >= 0 and k >= 0 else -1)


f = lambda : map(int, input().split())
(n, k) = f()
(s, d) = ([], -1)
for q in f():
	if q < 0:
		k -= 1
		if d > 0:
			s += [d]
		d = 0
	elif d + 1:
		d += 1
s.sort()

def g(k, d):
	d += len(s) << 1
	for q in s:
		if q > k:
			break
		k -= q
		d -= 2
	return d
print(0 if d < 0 else -1 if k < 0 else g(k, 2) if k < d else min(g(k, 2), g(k - d, 1)))


import sys
from collections import deque

def weather(temp):
	return temp >= 0
INF = int(1000000.0)
(n, k) = (int(x) for x in input().split())
day_to_temp = [int(x) for x in input().split()]
day_to_weather = [weather(temp) for temp in day_to_temp]
first_warm = -1
mid_warms = []
colds = []
curr_state = 0
curr_len = 0
switches_made = 0
for weather in day_to_weather:
	if curr_state == 0:
		if weather == 1:
			curr_len += 1
		else:
			first_warm = curr_len
			curr_state = 2
			curr_len = 1
			switches_made += 1
	elif curr_state == 1:
		if weather == 1:
			curr_len += 1
		else:
			mid_warms.append(curr_len)
			curr_state = 2
			curr_len = 1
			switches_made += 1
	elif weather == 1:
		colds.append(curr_len)
		curr_state = 1
		curr_len = 1
		switches_made += 1
	else:
		curr_len += 1
if curr_state == 1:
	last_warm = curr_len
elif curr_state == 2:
	colds.append(curr_len)
	last_warm = INF
else:
	print(0)
	sys.exit()
mid_warms_deque = deque(sorted(mid_warms, reverse=True))
cold_days_nr = sum(colds)
free_days = k - cold_days_nr
if free_days < 0:
	print(-1)
	sys.exit()
elif free_days == 0:
	print(switches_made)
	sys.exit()
elif len(mid_warms) > 0:
	while mid_warms_deque:
		curr_warm_len = mid_warms_deque.pop()
		if not free_days - curr_warm_len >= 0:
			break
		switches_made -= 2
		free_days -= curr_warm_len
if free_days - last_warm >= 0:
	switches_made -= 1
	free_days -= last_warm
print(switches_made)


import sys

def weather(temp):
	return temp >= 0
INF = int(1000000.0)
(n, k) = (int(x) for x in input().split())
day_to_temp = [int(x) for x in input().split()]
day_to_weather = [weather(temp) for temp in day_to_temp]
first_warm = -1
mid_warms = []
colds = []
curr_state = 0
curr_len = 0
switches_made = 0
for weather in day_to_weather:
	if curr_state == 0:
		if weather == 1:
			curr_len += 1
		else:
			first_warm = curr_len
			curr_state = 2
			curr_len = 1
			switches_made += 1
	elif curr_state == 1:
		if weather == 1:
			curr_len += 1
		else:
			mid_warms.append(curr_len)
			curr_state = 2
			curr_len = 1
			switches_made += 1
	elif weather == 1:
		colds.append(curr_len)
		curr_state = 1
		curr_len = 1
		switches_made += 1
	else:
		curr_len += 1
if curr_state == 1:
	last_warm = curr_len
elif curr_state == 2:
	colds.append(curr_len)
	last_warm = INF
else:
	print(0)
	return
mid_warms = sorted(mid_warms)
cold_days = sum(colds)
free_days = k - cold_days
if free_days < 0:
	print(-1)
	return
elif free_days == 0:
	print(switches_made)
	return
elif len(mid_warms) > 0:
	i = 0
	while i < len(mid_warms) and free_days - mid_warms[i] >= 0:
		switches_made -= 2
		free_days -= mid_warms[i]
		i += 1
if free_days - last_warm >= 0:
	switches_made -= 1
	free_days -= last_warm
print(switches_made)


def ri():
	return list(map(int, input().split()))
(n, k) = ri()
t = list(ri())
tt = []
mc = 0
for i in range(n):
	if i == 0:
		if t[i] < 0:
			tt.append(-1)
			mc += 1
		else:
			tt.append(1)
		continue
	if t[i] < 0:
		mc += 1
		if t[i - 1] >= 0:
			tt.append(-1)
		continue
	elif t[i - 1] >= 0:
		tt[-1] = tt[-1] + 1
	else:
		tt.append(1)
if mc > k:
	print(-1)
	return
if tt[0] != -1:
	tt = tt[1:]
if len(tt) == 0:
	print(0)
	return
ttt = []
maxs = len(tt)
k2 = k
tt2 = tt[:]
if tt[-1] != -1:
	tt = tt[:-1]
for i in tt:
	if i > 0:
		ttt.append(i)
k -= mc
ttt.sort()
for i in ttt:
	if k - i >= 0:
		k -= i
		maxs -= 2
	else:
		break
ttt2 = []
maxs2 = len(tt2)
for i in tt2:
	if i > 0:
		ttt2.append(i)
k2 -= mc
check = 0
ttt2.sort()
for i in ttt2:
	if k2 - i >= 0:
		k2 -= i
		maxs2 -= 2
		if i == tt2[-1] and check == 0:
			maxs2 += 1
			check = 1
	else:
		break
print(min(maxs, maxs2))


from collections import deque
import heapq

def main():
	from sys import stdin
	lines = deque((line.strip() for line in stdin.readlines()))
	(n, k) = [int(x) for x in lines.popleft().split()]
	temps = deque((int(x) for x in lines.popleft().split()))
	temps.appendleft(0)
	streaks = []
	count = 0
	ispositive = True
	numnegative = 0
	changes = 0
	while temps:
		temp = temps.popleft()
		positive = temp >= 0
		if positive:
			count += 1
			if not ispositive:
				changes += 1
		else:
			numnegative += 1
			if ispositive:
				streaks.append(count)
				count = 0
				changes += 1
		ispositive = positive
	if numnegative == 0:
		print(0)
		return
	if numnegative > k:
		print(-1)
		return
	if k >= n:
		print(1)
		return
	k -= numnegative
	heap = streaks[1:]
	heapq.heapify(heap)
	heap2 = list(heap)
	if ispositive:
		heapq.heappush(heap2, count)
	changes2 = changes
	k2 = k
	while heap and k >= heap[0]:
		k -= heapq.heappop(heap)
		changes -= 2
	if ispositive and k > count:
		changes -= 1
	while heap2 and k2 >= heap2[0]:
		k2 -= heapq.heappop(heap2)
		changes2 -= 2
	if ispositive and (not heap2 or heap2[0] > count):
		changes2 += 1
	print(min(changes, changes2))
main()


from collections import Counter

def f(arr, k):
	neg = []
	for i in range(0, len(arr)):
		if arr[i] < 0:
			neg.append(i)
	k -= len(neg)
	if k < 0:
		return -1
	dif = []
	ans = len(neg) * 2
	for i in range(len(neg) - 1):
		dif.append(neg[i + 1] - neg[i] - 1)
	dif = sorted(dif)
	for i in dif:
		if k >= i:
			k -= i
			ans -= 2
		else:
			break
	if neg:
		if len(arr) - 1 - neg[-1] <= k:
			ans -= 1
	return ans
(a, b) = map(int, input().strip().split())
lst = list(map(int, input().strip().split()))
print(f(lst, b))


(n, k) = list(map(int, input().split()))
a = list([int(x) >= 0 for x in input().split()])
for ind_positive in range(n):
	if not a[ind_positive]:
		break
else:
	print(0)
	return
a = a[ind_positive:]
n = len(a)
for ind_positive in range(n - 1, -1, -1):
	if not a[ind_positive]:
		break
a = a[:ind_positive + 1]
len_suf = n - ind_positive - 1
n = len(a)
b = []
i = 0
while True:
	j = 0
	while i < n and a[i]:
		i += 1
		j += 1
	if j:
		b.append(j)
	i += 1
	if i >= n:
		break
b_sort = b.copy()
b_sort.sort(reverse=True)
s = 0
i = 0
if n - s > k:
	for i in range(len(b)):
		s += b_sort[i]
		if n - s <= k:
			i += 1
			break
if n - s > k:
	ans2 = -1
else:
	ans2 = i * 2 + 2
k -= len_suf
if k < 0:
	ans1 = -1
else:
	b = []
	i = 0
	while True:
		j = 0
		while i < n and a[i]:
			i += 1
			j += 1
		if j:
			b.append(j)
		i += 1
		if i >= n:
			break
	b_sort = b.copy()
	b_sort.sort(reverse=True)
	s = 0
	i = 0
	if n - s > k:
		for i in range(len(b)):
			s += b_sort[i]
			if n - s <= k:
				i += 1
				break
	if n - s > k:
		ans1 = -1
	else:
		ans1 = i * 2 + 1
if ans1 == -1:
	print(ans2)
elif ans2 == -1:
	print(ans1)
else:
	print(min(ans1, ans2))


(n, k) = list(map(int, input().split()))
winter = []
for (i, t) in enumerate([int(n) for n in input().split()]):
	if t < 0:
		winter.append(i)
if len(winter) > k:
	print(-1)
else:
	ans = len(winter) * 2
	k -= len(winter)
	for diff in sorted([winter[i] - winter[i - 1] - 1 for i in range(1, len(winter))]):
		if k >= diff:
			k -= diff
			ans -= 2
	print(ans - (1 if len(winter) > 0 and k >= n - winter[-1] - 1 else 0))


import math
from collections import Counter, defaultdict
from itertools import accumulate
R = lambda : map(int, input().split())
(n, k) = R()
ts = list(R()) + [-1]
k -= sum((1 if t < 0 else 0 for t in ts[:n]))
res = 0 if ts[0] >= 0 else 1
for i in range(1, n):
	if ts[i - 1] < 0 and ts[i] >= 0 or (ts[i - 1] >= 0 and ts[i] < 0):
		res += 1
locs = [i for (i, t) in enumerate(ts) if t < 0]
ps = sorted(((y - x - 1, y) for (x, y) in zip(locs, locs[1:]) if y - x > 1))
res1 = res
k1 = k
for p in ps:
	if k >= p[0]:
		res -= 2 if p[1] < n else 1
		k -= p[0]
	if k1 >= p[0] and p[1] < n:
		res1 -= 2
		k1 -= p[0]
res = res if k >= 0 else math.inf
res1 = res1 if k1 >= 0 else math.inf
print(min(res, res1) if min(res, res1) < math.inf else -1)


(n, k) = map(int, input().split())
temp = list(map(int, input().split()))
rslt = []
list = []
cnt = 0
for i in range(n):
	if temp[i] < 0:
		rslt.append(i)
		cnt += 1
if cnt > k:
	print(-1)
	exit()
if cnt == 0:
	print(0)
	exit()
k -= cnt
ans = 2 * cnt
for i in range(cnt - 1):
	list.append(rslt[i + 1] - rslt[i] - 1)
list.sort()
for i in list:
	if k < i:
		break
	k -= i
	ans -= 2
if k >= n - rslt[cnt - 1] - 1:
	ans -= 1
print(ans)


(n, k) = [int(i) for i in input().split()]
t = [int(i) for i in input().split()]
colddays = [i for i in range(n) if t[i] < 0]
num_colddays = len(colddays)
if num_colddays == 0:
	print(0)
elif k >= n:
	print(1)
elif num_colddays > k:
	print(-1)
else:
	k -= num_colddays
	ans = 0
	for i in range(1, len(colddays)):
		if colddays[i] - colddays[i - 1] > 1:
			ans += 1
	ans += 1
	ans *= 2
	gap = [0 for i in range(num_colddays)]
	for j in range(1, num_colddays):
		gap[j - 1] = colddays[j] - colddays[j - 1] - 1
	positivegap = [j for j in gap if j > 0]
	positivegap = sorted(positivegap)
	for i in positivegap:
		if k >= i:
			k -= i
			ans -= 2
		else:
			break
	remain = n - 1 - colddays[-1]
	if k >= remain:
		ans -= 1
	print(ans)


(n, k) = [int(i) for i in input().split(' ')]
w = [int(i) for i in input().split(' ')]
f = 0
while f < n and w[f] >= 0:
	f += 1
if f == n:
	print(0)
	exit()
b = n - 1
while b >= 0 and w[b] >= 0:
	b -= 1
if f == b:
	if k == 0:
		print(-1)
		exit()
	if f + 1 == n:
		print(1)
		exit()
	elif k - 1 >= n - (b + 1):
		print(1)
		exit()
	else:
		print(2)
		exit()
inv = []
ps = 0
ns = 0
for i in range(f, b):
	if w[i] >= 0:
		ps += 1
		if w[i + 1] < 0:
			inv.append(ps)
	elif w[i] < 0:
		ns += 1
		if w[i + 1] >= 0:
			ps = 0
ns += 1
spare = k - ns
if spare < 0:
	print(-1)
	exit()
if not inv:
	if w[n - 1] < 0:
		print(1)
		exit()
	elif spare >= n - (b + 1):
		print(1)
		exit()
	else:
		print(2)
		exit()
invs = sorted(inv)
if spare < invs[0]:
	ch = (len(invs) + 1) * 2
	remainder = spare
else:
	(use, invsn) = (invs[0], -1)
	for i in range(1, len(invs)):
		use += invs[i]
		if spare < use:
			use -= invs[i]
			invsn = i
			break
	if invsn == -1:
		invsn = len(invs)
	ch = (len(invs) - invsn + 1) * 2
	remainder = spare - use
if remainder >= n - (b + 1):
	ch -= 1
print(ch)


import sys
inp = sys.stdin.readline

def input():
	return inp().strip()
flush = sys.stdout.flush

def iin():
	return int(input())

def lin():
	return list(map(int, input().split()))

def main():
	(n, k) = lin()
	a = lin()
	a1 = [0] * n
	for i in range(n):
		if a[i] < 0:
			a1[i] = 1
	sm = sum(a1)
	if sm > k:
		print(-1)
	else:
		sm = k - sm
		lft = []
		ch = 0
		for i in range(n):
			if a1[i]:
				if ch and i - ch:
					lft.append([ch, i - ch, 2])
				ch = 0
			else:
				ch += 1
		ext = []
		if ch and i + 1 - ch:
			ext = [ch, 1 + i - ch, 1]
		lft.sort()
		a2 = lft + ([ext] if ext else [])
		a2.sort()

		def check(a):
			if not a:
				return 0
			s1 = sm
			ans = 0
			for (i, j, k) in a:
				if s1 < i:
					break
				s1 -= i
				ans += k
			return ans
		if check(a2) > check(lft):
			lft = a2
		lft = lft[::-1]
		while sm and lft:
			(ch, i, asd) = lft.pop()
			if sm < ch:
				continue
			while sm and ch and (i < n):
				a1[i] = 1
				i += 1
				sm -= 1
				ch -= 1
		ans = 0
		a1 = [0] + a1
		for i in range(1, n + 1):
			if a1[i] != a1[i - 1]:
				ans += 1
		print(ans)
main()


(n, k) = list(map(int, input().split()))
days = list(map(int, input().split()))
a = [0 for i in range(n)]
b = [0 for i in range(n)]
asum = 0
ia = 0
ib = 0
inf = n + 199
for x in days:
	if x < 0:
		a[ia] += 1
		asum += 1
		if b[ib] != 0:
			ib += 1
	else:
		b[ib] += 1
		if a[ia] != 0:
			ia += 1
changes = ia + 1 if a[ia] > 0 else ia
changes += changes - 1
if a[ia] == 0:
	ia -= 1
if b[ib] == 0:
	ib -= 1
if asum > k:
	print(-1)
	quit()
for i in range(ia, n):
	a[i] = inf if a[i] == 0 else a[i]
for i in range(ib, n):
	b[i] = inf if b[i] == 0 else b[i]
if days[0] >= 0:
	b[0] = inf
lastb = -1
removedlastb = False
if days[len(days) - 1] >= 0:
	changes += 1
	lastb = b[ib]
b.sort()
curb = 0
seccurb = curb
secasum = asum
secchanges = changes
secremovedlastb = removedlastb
while curb <= ib and asum + b[curb] <= k:
	asum += b[curb]
	if not removedlastb:
		if b[curb] == lastb:
			changes -= 1
			removedlastb = True
		else:
			changes -= 2
	else:
		changes -= 2
	curb += 1
while seccurb <= ib and secasum + b[seccurb] <= k:
	secasum += b[seccurb]
	if not secremovedlastb:
		if b[seccurb] == lastb:
			secasum -= b[seccurb]
			secremovedlastb = True
		else:
			secchanges -= 2
	else:
		secchanges -= 2
	seccurb += 1
print(max(min(changes, secchanges), 0))


import heapq
(n, k) = [int(i) for i in input().split()]
l = [int(i) for i in input().split()]
cnt = [i for i in l if i < 0]
m = 0
for (a, i) in enumerate(l):
	if i < 0 and m == 0:
		m = 1
	elif i < 0 and l[a - 1] >= 0:
		m += 1
d = {}
q = []
chk = -1
for i in l:
	if i < 0:
		if chk > 0:
			if chk in d:
				d[chk] += 1
			else:
				d[chk] = 1
				heapq.heappush(q, chk)
		chk = 0
	elif chk >= 0:
		chk += 1
ans = m * 2
k -= len(cnt)
while len(q) and k >= q[0]:
	k -= q[0]
	ans -= 2
	d[q[0]] -= 1
	if d[q[0]] == 0:
		heapq.heappop(q)
if k >= chk and chk > -1:
	ans -= 1
print(ans if ans >= 0 and k >= 0 else -1)


(_, k) = map(int, input().split())
val = [0] + list(map(int, input().split()))
n = len(val)
pls = []
(cur, i, sm) = (0, 0, 0)
while i < n:
	if val[i] >= 0:
		cur += 1
	else:
		if cur > 0:
			pls.append(cur)
		cur = 0
	i += 1
sm = sum((p for p in pls))
pls = pls[1:]
if cur > 0:
	one = cur
	sm += cur
else:
	one = 10 ** 19
ans = 0
for i in range(1, n):
	if val[i] >= 0 and val[i - 1] < 0 or (val[i] < 0 and val[i - 1] >= 0):
		ans += 1
if n - sm > k:
	print(-1)
else:
	pls.sort()
	rem = k - (n - sm)
	for p in pls:
		if rem >= p:
			rem -= p
			ans -= 2
	if rem >= one:
		ans -= 1
	print(ans)


def solve(k, s):
	w = [0]
	for c in s:
		if c < 0:
			if w[-1] >= 0:
				w.append(-1)
			else:
				w[-1] -= 1
		elif w[-1] < 0:
			w.append(1)
		else:
			w[-1] += 1
	(begin, end) = (w[0], w[-1])
	if len(w) == 1 and w[0] > 0:
		return 0
	if begin > 0:
		w.pop(0)
	if end > 0:
		w.pop()
	neg_seg = [t for t in w if t < 0]
	pos_seg = [t for t in w if t > 0]
	d = -sum(neg_seg)
	if d > k:
		return -1
	changes = 2 * len(neg_seg) - (end < 0)
	pos_seg.sort()
	for seg in pos_seg:
		d += seg
		if d > k:
			if end > 0 and d - seg + end <= k:
				return changes - 1
			else:
				return changes
		else:
			changes -= 2
	if end > 0 and d + end <= k:
		return changes - 1
	else:
		return changes
(n, k) = map(int, input().split())
s = [int(x) for x in input().split()]
print(solve(k, s))


f = lambda : map(int, input().split())
(n, k) = f()
(s, d) = ([], -1)
for q in f():
	if q < 0:
		k -= 1
		if d > 0:
			s += [d]
		d = 0
	elif d > -1:
		d += 1
s.sort()
t = 2 * len(s)
for q in s:
	if q > k:
		break
	k -= q
	t -= 2
print(-1 if k < 0 else 0 if d < 0 else 2 + t - (k >= d))