Waterloo 2025 Fall E - Efficient Room Scheduling

View as PDF

Submit solution

Points: 5
Time limit: 1.0s
Memory limit: 256M

Problem type

The 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 100. The first line of each test case contains two integers between 1 and 20\,000 inclusive, indicating the number n of lectures to be scheduled and the number m of rooms in the university. The next n lines each contain an integer, the number of students in each lecture. The following m 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

There are no comments at the moment.