Для перевозки партии грузов различной массы выделен грузовик, но его грузоподъёмность ограничена, поэтому перевезти сразу все грузы не удастся. Грузы массой от 200 до 230 кг включительно грузят в первую очередь, выбирая грузы по убыванию массы, начиная с самого тяжёлого. На оставшееся после этого место стараются взять как можно большее количество грузов. Если это можно сделать несколькими способами, выбирают тот способ, при котором самый большой из выбранных грузов имеет наибольшую массу. Если и при этом условии возможно несколько вариантов, выбирается тот, при котором наибольшую массу имеет второй по величине груз, и т.д. Известны количество грузов, масса каждого из них и грузоподъёмность грузовика. Необходимо определить количество и общую массу грузов, которые будут вывезены при погрузке по вышеописанным правилам.
Входные данные представлены в файле 26_2.txt следующим образом. В первой строке входного файла записаны два целых числа: N – общее количество грузов и M – грузоподъёмность грузовика в кг. Каждая из следующих N строк содержит одно целое число – массу груза в кг. В ответе запишите два целых числа через пробел: сначала максимально возможное количество грузов, затем их общую массу.
Пример организации исходных данных во входном файле:
6 900
100
210
215
160
240
300
В данном случае сначала нужно взять груз массой 210 и 215 кг. Остается 475 кг. После этого можно вывезти ещё максимум 2 груза. Это можно сделать пятью способами: 100 + 160, 100 + 240, 100+300, 160 + 240, 160+300. Выбираем способ, при котором вывозится груз наибольшей возможной массы. Таких способов два: 100 +300, 160+300. Из этих способов выбираем тот, при котором больше масса второго по величине груза, то есть 160+300. Всего получается 4 груза общей массой 885 кг. Ответ: 4 885.