Кухня Тома
Кухня Тома - очень популярный ресторан. Одна из причин его популярности заключается в том, что каждое блюдо готовится как минимум 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".