Vote Counting

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

At eight o’clock in the evening, all polling stations close, and the election commissions begin counting votes. Let’s consider the vote-counting process by a certain election commission. Let there be a Commission Chairperson and \(n\) commission members (excluding the Chairperson). Also, let there be a total of \(m\) ballot boxes at the polling station. Each ballot box has a unique number (an integer from 1 to \(m\)). It is known that the ballot box with number \(i\) contains \(a_i\) ballots.

Thus, the commission members sit at a large table, and the Commission Chairperson distributes the ballot boxes to them for counting. Each commission member receives a certain number of ballot boxes, and the numbers of these ballot boxes must be consecutive. That is, a commission member can receive ballot boxes with numbers [4, 5, 6, 7] or [1, 2, 3], but cannot receive ballot boxes with numbers [4, 7, 47].

After the distribution, it may happen that some number of commission members are left without work — they do not get any ballot boxes. Your task is — knowing the maximum number of ballots \(k\) that one commission member can count, to state the maximum possible number of commission members that can be left without work.

Input

The first line contains three natural numbers \(n\), \(m\), and \(k\) — the number of commission members, the number of ballot boxes, and the maximum number of ballots for a single commission member, respectively.

The second line contains \(m\) natural numbers \(a_i\) — the number of ballots in the respective ballot boxes.

Output

In a single line, output a single non-negative integer — the maximum possible number of commission members left without work, or -1 if there are not enough commission members to count all the ballots.

Constraints

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

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

Samples