eolymp
bolt
Try our new interface for solving problems
Problems

Tom's Kitchen

Tom's Kitchen

Time limit 1 second
Memory limit 128 MiB

Tom's Kitchen is a very popular restaurant. One of the reasons for its popularity is that every single meal is prepared by at least k different chefs. Today, there are n meals to be prepared, with meal i needing a[i] hours of work.

There are m chefs which Tom can hire to prepare all the meals but the chef j will work at most b[j] hours. Additionally, even when he works less, he still wants to be paid for the full b[j] hours. A chef can work on several meals for different amounts of time, but any meal will be properly prepared only if at least k chefs take part in preparing it and the total time they spend is exactly a[i]. When a chef takes part in preparing a meal, he always works on it some positive integer number of hours.

Tom needs help in choosing the optimal subset of chefs such that the sum of hours where the chefs are getting paid without working is minimised.

Input data

First line contains integers n, m and k. Second line contains n integers a[i] and the third line m integers b[j].

Output data

The only line should contain the number of hours the chefs spend not working but still getting paid when Tom chooses the optimal subset to hire. If there is no way to prepare all the n meals according to the rules described above, output "Impossible".

Examples

Input example #1
1 2 2
5
3 4
Output example #1
2
Source 2019 Baltic Olympiad in Informatics, Day 2, 27 Apr - 2 May