Baltic Olympiad in Informatics: 2019 Day 2, Problem 1
Tom's Kitchen is a very popular restaurant.
One of the reasons for its popularity is that every single meal is prepared by at least
There are
Tom needs help in choosing the optimal subset of chefs such that the sum of hours where the chefs are getting paid without working is minimized.
Input Specification
The first line contains the integers
The second line contains
Output Specification
The only line should contain the number of hours the chefs spend not working but still getting paid when Tom chooses the optimal subset to hire.
If there is no way to prepare all the Impossible
.
Sample Input 1
1 2 2
5
3 4
Sample Output 1
2
Explanation for Sample Output 1
Here Tom needs two chefs to work on the meal, so he must hire both that are available.
Then it does not matter how they divide the work, as they end up working a total of 5 hours, but getting paid for
Sample Input 2
1 1 2
5
5
Sample Output 2
Impossible
Explanation for Sample Output 2
Here Tom needs two chefs to work on the meal, but only one is available.
Sample Input 3
3 3 3
3 3 2
3 3 3
Sample Output 3
Impossible
Here meal 3 can't be prepared by three chefs, as each would have to work for at least an hour, but the meal takes only 2 hours to prepare.
Grading
The subtasks satisfy the following conditions:
- (
points) , , . - (
points) , , . - (
points) , . - (
points) . - (
points) .
Comments