Baltic OI '19 P4 - Tom's Kitchen

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Python 5.0s
Memory limit: 256M

Problem type
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 K different chefs. Today, there are N meals to be prepared, with meal i needing A_i hours of work.

There are M chefs which Tom can hire to prepare all the meals but the chef j will work at most B_j hours. Additionally, even when he works less, he still wants to be paid for the full B_j hours. A chef can work on several meals for different amounts of time, but any meal will be properly prepared only if at least K chefs take part in preparing it and the total time they spend is exactly A_i. When a chef takes part in preparing a meal, he always works on it some positive integer number of hours.

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 N, M, and K.

The second line contains N integers A_i and the third line M integers B_j.

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 N meals according to the rules described above, output Impossible.

Sample Input 1

1 2 2
3 4

Sample Output 1


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 3+4 = 7 hours, and thus getting paid for 2 extra hours.

Sample Input 2

1 1 2

Sample Output 2


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


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.


The subtasks satisfy the following conditions:

  1. (9 points) 1 \le N, K \le 300, 1 \le M \le 2, 1 \le A_i, B_j \le 300.
  2. (22 points) 1 \le N, K \le 300, 1 \le M \le 15, 1 \le A_i, B_j \le 300.
  3. (20 points) 1 \le N, M, A_i, B_j \le 300, K = 1.
  4. (21 points) 1 \le N, M, K, A_i, B_j \le 40.
  5. (28 points) 1 \le N, M, K, A_i, B_j \le 300.


There are no comments at the moment.