Tom의 주방

시간 제한2초메모리 제한512 MB

요약

각 요리에 최소 K명의 셰프가 양의 정수 시간씩 일해 정확히 A_i시간을 채우도록 셰프 부분집합을 고르고, 셰프에게 지급하는 유휴 시간을 최소화합니다.

난이도: 어려움10점 중 8점
유형: 그래프, 그리디
정답자: 아직 제출이 없습니다

문제

Tom의 주방은 매우 인기 있는 식당이다. 인기의 이유 중 하나는 모든 음식이 최소 $K$ 명의 서로 다른 요리사가 만든다는 점이다. 오늘 준비할 음식은 $N$ 개이며, 음식 $i$ 에는 $A_i$ 시간의 작업이 필요하다.

Tom은 $M$ 명의 요리사를 고용할 수 있다. 요리사 $j$ 는 최대 $B_j$ 시간까지 일한다. 요리사가 그보다 적게 일하더라도 $B_j$ 시간 전체에 대한 급여를 받는다. 요리사는 여러 음식에서 서로 다른 시간만큼 일할 수 있다. 음식이 규칙에 맞게 제대로 준비되려면, 그 음식을 만드는 요리사가 최소 $K$ 명이고 그들이 쓴 시간의 합이 정확히 $A_i$ 여야 한다. 요리사가 어떤 음식을 만드는 데 참여하면 항상 양의 정수 시간만큼 일한다.

Tom은 일하지 않고 급여만 받는 시간의 합이 최소가 되도록 요리사의 부분집합을 골라야 한다.

입력

첫째 줄에 정수 $N$ , $M$ , $K$ 가 주어진다. 둘째 줄에는 $N$ 개의 정수 $A_i$ 가, 셋째 줄에는 $M$ 개의 정수 $B_j$ 가 주어진다.

출력

Tom이 최적의 부분집합을 골랐을 때, 일하지 않고 급여만 받는 시간의 합의 최솟값을 출력한다. 모든 음식을 규칙에 맞게 준비할 방법이 없으면 "Impossible"을 출력한다.

예제3

예제 1
입력
```
1 2 2
5
3 4
```
예상 출력
```
2
```
예제 2
입력
```
1 1 2
5
5
```
예상 출력
```
Impossible
```
예제 3
입력
```
3 3 3
3 3 2
3 3 3
```
예상 출력
```
Impossible
```