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 students, where each student will take snacks. At the front of the line, there is a table which can hold at most snacks. At the table, there are volunteers putting snacks on the table. Every second, each of the volunteers puts 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 snacks, they will wait at the table until they have taken snacks.
The volunteers will also not exceed the limit of snacks the table has, e.g. if the table can only hold snack, and there are volunteers, then only 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 seconds of lunch.
What is the minimum number of volunteers that Muhammad needs to recruit, and is it even possible to get to everyone in the line?
Constraints
Subtask 1 [20%]
Subtask 2 [80%]
No additional constraints.
Input Specification
The first line of input will contain the integers , , and separated by a space.
The next line of input will contain space separated integers, where the integer represents the number of snacks the 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 second: volunteers each put a snack on the table, there are snacks on the table, then the first person takes snack, leaving snack left on the table.
During the second: volunteers each put a snack on the table, there are snacks on the table, then the second person takes snacks, leaving snack left on the table.
During the second: volunteers each put a snack on the table, there are snacks on the table, then the third person takes snack, leaving snacks left on the table.
During the second: volunteers each try to put a snack on the table. However, only one volunteer can place a snack on the table as . There are snacks on the table. The fourth person, being particularly greedy, wants to take snacks, so they take the on the table, and they stay in line. There are snacks left on the table.
During the second: volunteers each put a snack on the table, there are snacks on the table, the fourth person takes snacks and leaves the line, leaving snacks left on the table.
During the second: volunteers each put a snack on the table, there are snacks on the table, the fifth person takes snack and leaves the line, leaving 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
Comments