#P3204. 「BalticOI 2019 Day2」汤姆的餐厅

「BalticOI 2019 Day2」汤姆的餐厅

题目描述

译自 BalticOI 2019 Day2 T1. Tom's Kitchen

Tom's Kitchen 是一家非常受欢迎的餐厅,其受欢迎的原因之一是每份菜都由至少 K K 名厨师进行准备。今天有 N N 份菜需要准备,第 i i 份菜的准备时间是 Ai A_i 小时。

Tom 可以雇佣 M M 名厨师,厨师 j j 最多可以工作 Bj B_j 小时。此外,即使厨师 j j 的工作时间不到 Bj B_j 小时,他也会得到工作 Bj B_j 小时的报酬。一名厨师可以花不同的时间准备不同的菜,但是每一道菜都需要由至少 K K 名厨师准备,并且他们花的时间总和恰好为 Ai A_i 。当一名厨师准备菜品时,他总会花正整数小时。

Tom 需要一套最优的雇佣厨师方案,以使得厨师不工作就获得报酬的小时数(即所有雇佣厨师的总工作时间上限与准备所有菜的总时间之差)尽可能小。

输入格式

第一行包含三个正整数:N,M,K N,M,K

第二行包含 N N 个整数 Ai A_i ,第三行包含 M M 个整数 Bj B_j

输出格式

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

1 2 2
5
3 4
2
1 1 2
5
5
Impossible
3 3 3
3 3 2
3 3 3
Impossible

数据范围与提示

各子任务的分值与数据规模如下:

子任务 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 分):1N,M,Ai,Bj300,K=1 1 \leq N,M,A_i,B_j \leq 300, K=1
子任务 4(21 分):1N,M,K,Ai,Bj40 1 \leq N,M,K,A_i,B_j \leq 40
子任务 5(28 分):1N,M,K,Ai,Bj300 1 \leq N,M,K,A_i,B_j \leq 300