Задача #6690

Ежегодно библиотека пополняет свой книжный фонд. На закупку новых книг выделяется определённая сумма, которую нельзя превысить.

На эту сумму библиотеке необходимо закупить максимальное количество книг, среди которых должны быть ровно две редкие книги, одна из которых имеет наименьшую стоимость, а другая - наибольшую, также все энциклопедии. Известно, что стоимость редких книг превышает 3000 рублей. Стоимость энциклопедий находится в диапазоне от 2000 до 3000 рублей включительно. Стоимость любой другой книги меньше 2000 рублей.

По заданной информации о выделенной сумме на покупку книг и стоимости каждого наименования определите максимальное количество книг, которые может приобрести библиотека, и стоимость самой дорогой книги, не относящейся к категории редких и энциклопедий, при условии, что в итоге будут куплено наибольшее количество книг.

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

В первой строке входного файла находятся два числа: S - выделенная на покупку книг сумма (натуральное число, не превышающее 500 000) и N - количество наименований книг (натуральное число, не превышающее 1000). В следующих N строках находятся значения стоимости книг каждого наименования (все числа натуральные, не превышающие 5000), каждое в отдельной строке.

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

Пример входного файла:

11000 8
200
3800
3500
500
3100
800
4100
2500

При таких исходных данных можно приобрести максимум 5 книг: две редкие стоимостью 3100 и 4100, одну энциклопедию за 2500 и две обычных стоимостью 200 и 800. Ответ для приведённого примера 5 800.