Description

Tom's Kitchen is a very popular restaurant. One of the reasons for its popularity is that every dish is prepared by at least $K$ chefs. Today, there are $N$ dishes to be prepared. The preparation time of dish $i$ is $A_i$ hours.

Tom can hire $M$ chefs. Chef $j$ can work at most $B_j$ hours. Also, even if chef $j$ works fewer than $B_j$ hours, he will still be paid for $B_j$ hours. A chef may spend different amounts of time preparing different dishes, but each dish must be prepared by at least $K$ chefs, and the sum of the time they spend is exactly $A_i$. When a chef prepares a dish, he always spends a positive integer number of hours.

Tom needs an optimal hiring plan to make the number of paid-but-not-worked hours (that is, the difference between the sum of the working time limits of all hired chefs and the total time needed to prepare all dishes) as small as possible.

Input Format

The first line contains three positive integers: $N, M, K$.

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

Output Format

If there is no plan that can complete the preparation of all dishes, output Impossible. Otherwise, output one integer: the minimum number of paid-but-not-worked hours.

1 2 2
5
3 4

2

1 1 2
5
5

Impossible

3 3 3
3 3 2
3 3 3

Impossible

Hint

Sample Explanation 1

Tom needs to hire these two chefs to complete the preparation of all dishes. The total time to prepare all dishes is $5$ hours, but Tom needs to pay for $3+4=7$ hours, so the chefs get paid for $2$ hours without working.

Sample Explanation 2

Preparing one dish requires at least two chefs, but only one chef can be hired, so it is impossible to complete the preparation.

Sample Explanation 3

The third dish cannot be prepared by three chefs, because the preparation time of the third dish is only $2$ hours (this means that if three chefs prepare the third dish, at least one chef would spend $0$ hours preparing it, which is not allowed by the statement).

Subtasks

The scores and data scales of the subtasks are as follows:

• Subtask 1 (9 points): $1 \leq N, K \leq 300, 1 \leq M \leq 2, 1 \leq A_i, B_j \leq 300$;
• Subtask 2 (22 points): $1 \leq N, K \leq 300, 1 \leq M \leq 15, 1 \leq A_i, B_j \leq 300$;
• Subtask 3 (20 points): $1 \leq N, M, A_i, B_j \leq 300, K=1$;
• Subtask 4 (21 points): $1 \leq N, M, K, A_i, B_j \leq 40$;
• Subtask 5 (28 points): $1 \leq N, M, K, A_i, B_j \leq 300$.

Translated by ChatGPT 5