eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Кухня Тома

Кухня Тома

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Кухня Тома - очень популярный ресторан. Одна из причин его популярности заключается в том, что каждое блюдо готовится как минимум k разными поварами. Сегодня имеется n блюд, которые нужно приготовить, еда i требует a[i] рабочих часов.

Имеется m поваров, которых Том может нанять для приготовления всех блюд, однако повар j может работать не более b[j] часов. Кроме того, даже когда он работает меньше, он все равно хочет получить оплату за b[j] полных часов. Шеф-повар может поработать над несколькими блюдами в течение разных промежутков времени, но любое блюдо будет приготовлено надлежащим образом, только если в его приготовлении принимают участие не менее k поваров, а общее время, которое они проводят, составляет в точности a[i]. Когда шеф-повар участвует в приготовлении еды, он всегда работает над ней целое число часов.

Тому нужна помощь в выборе оптимального набора поваров, чтобы сумма часов, в которых им платят за простой, была минимальной.

Вхідні дані

Первая строка содержит целые числа n, m и k. Вторая строка содержит n целых чисел a[i], третья строка содержит m целых чисел b[j].

Вихідні дані

Выведите количество часов, которые шеф-повара тратят не работая, но получают за них оплату, при оптимальном найме Томом. Если невозможно приготовить все n блюд в соответствии с правилами, выведите "Impossible".

Приклад

Вхідні дані #1
1 2 2
5
3 4
Вихідні дані #1
2
Джерело 2019 Балтийская олимпиада по информатике, День 2, 27 Апр - 2 Май