Waterloo 2025 Fall E - Efficient Room Scheduling
View as PDFThe university is facing a difficult financial situation and is looking for ways to save as much money as possible. One way to help save money is to pack lectures into rooms that are as small as possible. A smaller room uses less heat and light than a larger room. Unused rooms can be left unheated with the lights turned off.
That said, each room has a maximum capacity that is strictly enforced. Each lecture must be scheduled in a room with at least as much capacity as the number of students in the lecture.
What is the most efficient way to allocate lectures to rooms, to minimize the total capacity of the rooms that are used? Rooms that are not used for any lecture do not count toward the total capacity.
Assume that all the lectures happen at the same time, so that at most one lecture can be allocated to a given room.
Input Specification
The input contains several test cases, at most .
The first line of each test case contains two integers between
and
inclusive, indicating the number
of lectures to be scheduled and the number
of rooms in the university.
The next
lines each contain an integer, the number of students in each lecture.
The following
lines each contain an integer, the capacity of each room.
The last test case is followed by a line containing 0 0.
Output Specification
For each test case, output a line containing the minimum total capacity of rooms that need to be allocated to lectures. If it is not possible to fit all the lectures in the rooms, output the
a line with the word Impossible.
Sample Input
2 3
5
4
7
8
4
2 1
5
5
10
0 0
Sample Output
11
Impossible
Comments