Задача #2148

(Л. Шастин) Группа исследователей отправляется на экспедицию в горы, где им нужно распределить свои припасы по нескольким хранилищам. У них есть N разновесных пакетов с продуктами, которые им нужно разместить в K пещерах, каждая из которых может вместить до M кг продуктов. Исследователи начинают последовательно заполнять пещеры по возрастанию их номеров: они помещают в каждую следующую пещеру сначала самый тяжелый из оставшихся пакетов, затем самый легкий, а потом снова самый тяжелый – и так поочередно до тех пор, пока в пещеру влезает следующий подходящий пакет. Определите наибольший номер неполной пещеры (в которой еще осталось свободное место) с наименьшим остатком свободного места в ней, а также общий остаток свободного места (в кг) во всех непустых пещерах.

Входные данные

В первой строке входного файла находится число N – количество пакетов с продуктами (натуральное число, не превышающее 10 000). Во второй строке находятся два числа: K – количество пещер и M - вместимость (в кг) каждой из пещер (K < M < 1 000 000). В третьей же строке находятся K чисел (каждое из них не превышает 10 000 000), характеризующих номера пещер. В следующих N строках находятся натуральные числа (каждое из них не превышает 100 000) – веса пакетов с продуктами (в кг).

Запишите в ответе два числа: сначала наибольший номер неполной пещеры с наименьшим остатком свободного места, а затем количество оставшегося свободного места во всех непустых пещерах (в кг).

Типовой пример организации данных во входном файле

5
3 7
7 9 4
6
4
1
5
2

При таких исходных данных пещеры с номерами 4 и 7 будут заполнены до отвала (6 + 1) и (5 + 2), а в последней пещере с номером 9 останется 3 кг свободного места (в неё погрузят последний пакет с весом 4 кг). Ответ: 9 3.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.