Berland 的冬天持续 n 天。对于每一天,我们都知道当天平均气温的预测。
Vasya 拥有一套新的冬季轮胎,这使他能够在任何平均气温下安全驾驶不超过 k 天。使用 k 天后(无论这些天的温度如何),这套冬季轮胎就会磨损,无法再使用。这 k 天不必形成连续的天段。
在第一个冬天之前,Vasya 仍然使用夏季轮胎。当平均气温非负值时,可以在任意天数内使用夏季轮胎安全行驶。在平均气温为负值的日子里,不可能使用夏季轮胎行驶。
Vasya 可以在任何一天开始时将夏季轮胎更换为冬季轮胎,反之亦然。
求 Vasya 需要将夏季轮胎更换为冬季轮胎的最少次数,反之亦然,以便在冬季安全驾驶。冬季结束时,汽车可以使用任何轮胎。
输入
第一行包含两个正整数 n 和 k (1 ≤ n ≤ 2·105, 0 ≤ k ≤ n) – 冬季天数和冬季轮胎可以使用的天数。允许在任何温度下使用冬季轮胎行驶,但总共不超过 k 天。
第二行包含 n 个整数的序列 t1, t2, ..., tn (- 20 ≤ ti ≤ 20) - 第 i 个冬季的平均气温。
输出
打印 Vasya 必须将夏季轮胎更换为冬季轮胎的最少次数,反之亦然,以便在整个冬季安全驾驶。如果不可能,则打印-1。
示例
输入 #1
4 3 -5 20 -3 0
输出 #1
2
输入 #2
4 2 -5 20 -3 0
输出 #2
4
输入 #3
10 6 2 -5 1 3 0 0 -4 -3 1 0
输出 #3
3
注意
在第一个示例中,在第一个冬季之前,Vasya 应该将夏季轮胎更换为冬季轮胎,使用三天,然后将冬季轮胎更换为夏季轮胎,因为他只需使用冬季轮胎三天就可以安全驾驶。因此,更换轮胎的总数等于两次。
在第二个示例中,在第一个冬季之前,Vasya 应将夏季轮胎更换为冬季轮胎,然后在第一个冬季之后将冬季轮胎更换为夏季轮胎。第二天之后,需要再次将夏季轮胎更换为冬季轮胎,第三天之后,需要将冬季轮胎更换为夏季轮胎。因此,更换轮胎的总数等于四。