Підрахунок голосів

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

О восьмій годині вечора всі виборчі дільниці зачиняються, і виборчі комісії починають підрахунок голосів. Розглянемо процес підрахунку голосів деякою виборчою комісією. Нехай в ній присутній Голова комісії та $n$ членів комісії (без Голови). Також нехай на виборчій дільниці всього є $m$ урн для голосування. Кожна урна має свій унікальний номер (ціле число від 1 до $m$). Відомо, що урна з номером $i$ містить $a_i$ бюлетенів.

Отож, члени комісії сідають за великий стіл, а Голова комісії розподіляє їм урни для підрахунку голосів. Кожен член комісії отримає деяку кількість урн, причому номери цих урн повинні йти підряд. Тобто член комісії може отримати урни з номерами [4, 5, 6, 7] або [1, 2, 3], але не може отримати урни з номерами [4, 7, 47].

Після розподілу може статися так, що деяка кількість членів виборчої комісії залишиться без роботи — їм не дістанеться жодної урни. Ваше завдання — знаючи максимальну кількість бюлетенів $k$, яку може порахувати один член комісії, сказати, яка максимально можлива кількість членів комісії може залишитися без роботи.

Вхідні дані

У першому рядку задано три натуральні числа $n$, $m$ та $k$ — кількість членів комісії, кількість урн для голосування та максимальну кількість бюлетенів для одного члена комісії відповідно.

У другому рядку задано $m$ натуральних чисел $a_i$ — кількості бюлетенів у відповідних урнах.

Вихідні дані

У єдиному рядку виведіть одне ціле невід’ємне число — максимальну можливу кількість членів комісії, що залишиться без роботи, або -1, якщо членів комісії не вистачить, щоб порахувати всі бюлетні.

Обмеження

$1 \le n, m \le 10^5$,

$1 \le a_i \le k \le 10^9$.

Приклади