Tom's Kitchen

Time limit2sMemory limit512 MB

Summary

Pick a subset of chefs so each meal gets at least K chefs working positive whole hours that sum exactly to A_i, minimizing the paid idle hours.

Level: Hard8 of 10
Topics: Graph, Greedy
Solved: No attempts yet

Problem

Tom's Kitchen is a very popular restaurant. One reason for its popularity is that every meal is prepared by at least $K$ different chefs. Today, there are $N$ meals to prepare, and meal $i$ needs $A_i$ hours of work.

Tom can hire $M$ chefs. Chef $j$ works at most $B_j$ hours. Even when a chef works less than that, the chef is paid for the full $B_j$ hours. A chef can work on several meals for different amounts of time. A meal is prepared properly 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, the chef always works a positive integer number of hours.

Tom needs to choose the subset of chefs that minimizes the total number of hours the chefs are paid for without working.

Input

The first line contains the integers $N$ , $M$ , and $K$ . The second line contains $N$ integers $A_i$ . The third line contains $M$ integers $B_j$ .

Output

Print the minimum total number of hours the chefs are paid for without working when Tom chooses the optimal subset. If there is no way to prepare all $N$ meals according to the rules, print "Impossible".

Examples3

Example 1
Input
```
1 2 2
5
3 4
```
Expected output
```
2
```
Example 2
Input
```
1 1 2
5
5
```
Expected output
```
Impossible
```
Example 3
Input
```
3 3 3
3 3 2
3 3 3
```
Expected output
```
Impossible
```