[BalticOI 2019 Day2]汤姆的餐厅

题目背景

**译自 [BalticOI 2019](http://boi2019.eio.ee/tasks/) Day2 T1.** ***[Tom's Kitchen](http://boi2019.eio.ee/wp-content/uploads/2019/05/kitchen.en_.pdf)***

题目描述

*Tom's Kitchen* 是一家非常受欢迎的餐厅,其受欢迎的原因之一是每份菜都由至少 $ K $ 名厨师进行准备。今天有 $ N $ 份菜需要准备,第 $ i $ 份菜的准备时间是 $ A_i $ 小时。 Tom 可以雇佣 $ M $ 名厨师,厨师 $ j $ 最多可以工作 $ B_j $ 小时。此外,即使厨师 $ j $ 的工作时间不到 $ B_j $ 小时,他也会得到工作 $ B_j $ 小时的报酬。一名厨师可以花不同的时间准备不同的菜,但是每一道菜都需要由至少 $ K $ 名厨师准备,并且他们花的时间总和恰好为 $ A_i $。当一名厨师准备菜品时,他总会花正整数小时。 Tom 需要一套最优的雇佣厨师方案,以使得厨师不工作就获得报酬的小时数(即所有雇佣厨师的总工作时间上限与准备所有菜的总时间之差)尽可能小。

输入输出格式

输入格式


第一行包含三个正整数:$ N,M,K $。 第二行包含 $ N $ 个整数 $ A_i $,第三行包含 $ M $ 个整数 $ B_j $。

输出格式


如果不存在一套方案可以完成所有菜的准备工作,输出 `Impossible`。否则输出一个整数,代表厨师不工作就获得报酬的小时数的最小值。

输入输出样例

输入样例 #1

1 2 2
5
3 4

输出样例 #1

2

输入样例 #2

1 1 2
5
5

输出样例 #2

Impossible

输入样例 #3

3 3 3
3 3 2
3 3 3

输出样例 #3

Impossible

说明

### 样例解释 1 Tom 需要雇佣这两位厨师来完成所有菜的准备工作。准备所有菜的时间为 $ 5 $ 小时,但 Tom 需要支付 $ 3+4=7 $ 小时的费用,即厨师不工作就能得到 $ 2 $ 小时的工资。 ### 样例解释 2 准备一份菜需要至少两位厨师,但只能雇佣一位厨师,因此不能完成准备工作。 ### 样例解释 3 第三份菜无法由三位厨师来准备,因为准备第三份菜的时间只有 $ 2 $ 小时(这意味着如果由三名厨师准备第三份菜的话,至少有一位厨师的准备时间是 $ 0 $ 小时,而这是不符合题目要求的)。 ### 子任务 各子任务的分值与数据规模如下: - 子任务 1(9 分):$ 1 \leq N,K \leq 300, 1 \leq M \leq 2, 1 \leq A_i,B_j \leq 300 $; - 子任务 2(22 分):$ 1 \leq N,K \leq 300, 1 \leq M \leq 15, 1 \leq A_i,B_j \leq 300 $; - 子任务 3(20 分):$ 1 \leq N,M,A_i,B_j \leq 300, K=1 $; - 子任务 4(21 分):$ 1 \leq N,M,K,A_i,B_j \leq 40 $; - 子任务 5(28 分):$ 1 \leq N,M,K,A_i,B_j \leq 300 $。