Задача про нульовий підрядок

Обмеження: 2 сек., 512 МіБ

Дано три цілі числа \(n\), \(m\) та \(k\). Також дано масив \(a\) довжини \(n\).

Можна виконувати два типи операцій:

1. Вибрати два індекси \(i\) та \(j\) (\(i \neq j\)) та поміняти місцями елементи \(a_i\) та \(a_j\). Таку операцію можна виконати не більше ніж \(k\) разів.

2. Зменшити будь-який елемент масиву на \(1\), якщо він більший за \(0\). Цю операцію можна виконувати будь-яку кількість разів.

Зеник виконує ці операції в довільному порядку та хоче зробити так, щоб після всіх операцій був проміжок довжини \(m\), що скадається лише з нулів.

Вхідні дані

У першому рядку задано три цілі числа \(n\), \(m\) та \(k\) — довжина масиву, довжина підмасиву, який Зеник хоче занулити, та максимальна кількість операцій першого типу.

У другому рядку задано \(n\) цілих чисел \(a_1, a_2, \ldots, a_n\) — елементи масиву.

Вихідні дані

Виведіть одне число — мінімальну кількість операцій другого типу, необхідну, щоб утворити підмасив, у якому всі елементи рівні нулю.

Обмеження

\(1 \le m \le n \le 4 \cdot 10^5\),

\(1 \le k \le 4 \cdot 10^5\),

\(1 \le a_i \le 10^9\).

Оцінювання складається з таких блоків:

• по 1 балу за кожен приклад з умови,

• 8 балів: \(n \le 2000, k = 1\),

• 14 балів: \(m \le k\),

• 17 балів: \(n \le 10^5, k \le 10\),

• 24 бали: \(n, k \le 10^5\),

• 35 балів: без додаткових обмежень.

Бали за блок ви отримаєте, тільки якщо ваша програма пройде всі тести з блоку.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 3 2 1 2 5 2 4 4 6	5

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 2 1 1 4 4 6 2	3

Примітки

В першому прикладі:

Ми використовуємо операцію першого типу та міняємо місцями елементи під номерами \(3\) та \(4\).

Після цього беремо підмасив довжини \(3\) з перших трьох елементів, він виглядає так: [1, 2, 2]

Щоб зробити всі його елементи рівними нулю, використовуємо операції другого типу. На це потрібно 5 операцій.

Це є найкраща відповідь для цього прикладу.