Muhammad is in charge of the nutrition program and needs more volunteers. However, he doesn't know how many volunteers he needs.

At lunch, there is a line of $N$ students, where each student will take $S_i$ snacks. At the front of the line, there is a table which can hold at most $K$ snacks. At the table, there are $M$ volunteers putting snacks on the table. Every second, each of the $M$ volunteers puts $1$ snack on the table. Then the student at the front of the line, and only the student at the front, will try to take some snacks. If the student hasn't taken their $S_i$ snacks, they will wait at the table until they have taken $S_i$ snacks.

The volunteers will also not exceed the limit of snacks the table has, e.g. if the table can only hold $1$ snack, and there are $2$ volunteers, then only $1$ volunteer will place a snack on the table.

However, the volunteers are on a tight schedule! They only agreed to hand out snacks for the first $T$ seconds of lunch.

What is the minimum $M$ number of volunteers that Muhammad needs to recruit, and is it even possible to get to everyone in the line?

Constraints

$1\le N\le {10}^5$

$1\le N\le T\le {10}^6$

$1\le K,S_i\le {10}^6$

Subtask 1 [20%]

$1\le N\le {10}^3$

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line of input will contain the integers $N$, $T$, and $K$ separated by a space.

The next line of input will contain $N$ space separated integers, where the $i^{\text{th}}$ integer represents the number of snacks $S_i$ the $i^{\text{th}}$ student will take.

Output Specification

Output the minimum number of volunteers Muhammad needs, or if it's not possible to get to everyone in line output -1.

Sample Input 1

5 7 3
1 2 1 5 1

Sample Output 1

2

Explanation for Sample 1

During the $1^{\text{st}}$ second: $2$ volunteers each put a snack on the table, there are $2$ snacks on the table, then the first person takes $1$ snack, leaving $1$ snack left on the table.

During the $2^{\text{nd}}$ second: $2$ volunteers each put a snack on the table, there are $3$ snacks on the table, then the second person takes $2$ snacks, leaving $1$ snack left on the table.

During the $3^{\text{rd}}$ second: $2$ volunteers each put a snack on the table, there are $3$ snacks on the table, then the third person takes $1$ snack, leaving $2$ snacks left on the table.

During the $4^{\text{th}}$ second: $2$ volunteers each try to put a snack on the table. However, only one volunteer can place a snack on the table as $K=3$. There are $3$ snacks on the table. The fourth person, being particularly greedy, wants to take $5$ snacks, so they take the $3$ on the table, and they stay in line. There are $0$ snacks left on the table.

During the $5^{\text{th}}$ second: $2$ volunteers each put a snack on the table, there are $2$ snacks on the table, the fourth person takes $2$ snacks and leaves the line, leaving $0$ snacks left on the table.

During the $6^{\text{th}}$ second: $2$ volunteers each put a snack on the table, there are $2$ snacks on the table, the fifth person takes $1$ snack and leaves the line, leaving $1$ snack left on the table.

It can be proven that this is the best answer.

Sample Input 2

3 3 10
1 1 11

Sample Output 2

-1