WEEL


Submit solution

Points: 100
Time limit: 1.0s
Memory limit: 493M

Problem type

Mùa đông ở Berland kéo dài n ngày. Mỗi ngày dự báo cho biết nhiệt độ không khí trung bình ngày hôm đó. CP có bộ lốp xe mùa đông mới cho phép anh ta lái xe an toàn không quá k ngày ở bất kì nhiệt độ nào. Không nhất thiết là phải sử dụng k ngày liên tiếp, Trước ngày mùa đông Before CP đang sử dụng lốp mùa hè. Có thể sử dụng lốp xe mùa hè bất kì ngày nào nếu nhiệt độ tb của ngày hôm đó không âm. Tức là nhiệt độ âm thì không thể sử dụng lốp xe mùa hè. CP có thể thay đổi lốp xe mùa hè thành lốp mùa đông hoặc ngược lại vào đầu của một ngày bất kì.

Yêu cầu: Tìm số lần thay lốp là nhỏ nhất để CP có thể lái xe an toàn cả mùa đông. Cuối mùa đông xe có thể đang dùng bất kì bộ lốp nào.

Input

Dòng đầu tiên chứ hai số nguyên n and k (1 ≤ n ≤ 2•10^5, 0 ≤ k ≤ n) — là số lượng ngày của mùa đông, và số ngày tối đa có thể đi bằng lốp mùa đông.

Dòng thứ hai chứa n số nguyên t1, t2, ..., tn ( - 20 ≤ ti ≤ 20) — lần lượt là nhiệt độ trung bình của n ngày trong mùa đông.

Output

In ra số lần thay lốp nhỏ nhất để CP có thể lái xe an toàn – nếu không có cách nào in ra -1

Sample Input

4 3
-5 20 -3 0

Sample Output

2

Sample Input

4 2
-5 20 -3 0

Sample Output

4

Comments

There are no comments at the moment.