Tom's Kitchen 是一家非常受欢迎的餐厅。它受欢迎的原因之一是每一道菜都由至少 $K$ 位不同的厨师准备。今天,有 $N$ 道菜需要准备,其中第 $i$ 道菜需要 $A_i$ 小时的工时。
Tom 可以雇佣 $M$ 位厨师来准备所有的菜,但第 $j$ 位厨师最多工作 $B_j$ 小时。此外,即使厨师实际工作的时间少于 $B_j$ 小时,他也必须获得 $B_j$ 小时的全额报酬。一位厨师可以参与多道菜的制作,且在每道菜上投入的时间可以不同。只有当至少 $K$ 位厨师参与某道菜的制作,且他们投入的总时间恰好为 $A_i$ 小时时,这道菜才算准备妥当。当一位厨师参与某道菜的制作时,他投入的时间必须是正整数小时。
Tom 需要帮助,以选择最优的厨师子集,使得厨师在未工作但仍获得报酬的时间总和最小。
输入格式
第一行包含整数 $N$、$M$ 和 $K$。
第二行包含 $N$ 个整数 $A_i$,第三行包含 $M$ 个整数 $B_j$。
输出格式
输出一行,包含 Tom 选择最优厨师子集时,厨师未工作但仍获得报酬的时间总和。如果无法按照上述规则准备好所有 $N$ 道菜,则输出 “Impossible”。
样例
样例输入 1
1 2 2 5 3 4
样例输出 1
2
说明:Tom 需要两位厨师来准备这道菜,因此他必须雇佣所有可用的两位厨师。无论他们如何分配工作,最终他们总共工作了 5 小时,但获得了 $3 + 4 = 7$ 小时的报酬,因此多付了 2 小时的报酬。
样例输入 2
1 1 2 5 5
样例输出 2
Impossible
说明:Tom 需要两位厨师来准备这道菜,但只有一位厨师可用。
样例输入 3
3 3 3 3 3 2 3 3 3
样例输出 3
Impossible
说明:第 3 道菜无法由三位厨师准备,因为每位厨师至少需要工作 1 小时,而这道菜只需要 2 小时。
子任务
测试组满足以下条件:
- (9 分) $1 \le N, K \le 300, 1 \le M \le 2, 1 \le A_i, B_j \le 300$。
- (22 分) $1 \le N, K \le 300, 1 \le M \le 15, 1 \le A_i, B_j \le 300$。
- (20 分) $1 \le N, M, A_i, B_j \le 300, K = 1$。
- (21 分) $1 \le N, M, K, A_i, B_j \le 40$。
- (28 分) $1 \le N, M, K, A_i, B_j \le 300$。