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

Обмеження: 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\).

Приклади