In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
Byteasar wants to take a taxi from the town Bytehole to the town Bytepit, which is kilometres away from Bytehole. Exactly kilometres along the way from Bytehole to Bytepit, there is a base of taxis, numbered from to . The taxi no. has enough fuel to drive exactly kilometres.
Byteasar can change taxis at any point. All the taxis start at their base but need not return there. Your task is to determine whether Byteasar can be driven from Bytehole to Bytepit, and if so, what it the minimum number of taxis required for such a journey.
The first line of the standard input holds three integers, , , and (, ), separated by single spaces. Those denote, respectively: the distance from Bytehole to Bytepit, the distance from Bytehole to the taxi base, and the number of taxis at the base. The second line of input contains integers, (), separated by single spaces. The number denotes the maximum distance (in kilometres) that the -th taxi can travel.
In tests worth 40% of all points an additional condition holds.
Your program should print a single integer to the standard output: the minimum number of taxis Byteasar has to take to get from Bytehole to Bytepit. If getting there is impossible, your program should print the number .
For the input data:
42 23 6 20 25 14 27 30 7
the correct result is:
Explanation of the example: Byteasar can take the taxis no. 4, 5, 1, and 2, in this order.
Task authors: Krzysztof Diks, Wojciech Rytter.<Submit a solution> [0/100]