G. Газета
Задачу добавил: alef
Успешно сдано решений: 8
Ограничение по времени: 2 с на тестОграничение по памяти: 256 Мб
Для посвящения в студенты старшекурсники задумали изготовить стенгазету, состоящую из M листов и повествующую об университете. Однако подготовительные работы они поручили первокурсникам.
Феофану выдали N листов ватмана одинаковой ширины, но разной длины, а также указание, что все заготовки для листов стенгазеты должны иметь одинаковую длину. Имеющиеся листы можно укорачивать, отрезая от них некоторую часть. При этом отрезанную часть в дальнейшем использовать нельзя (старшекурсники очень суеверны и забирают ее на шпаргалки). Листы также нельзя наращивать (использование клея крайне неблаготворно сказывается на текстах и рисунках).
Старшекурсники поручили Феофану выбрать из имеющихся листов M штук таким образом, чтобы суммарная длина отрезанного была минимальной. Если существует несколько вариантов такого выбора, они предпочтут тот, в котором длина листов стенгазеты будет максимальной.
Ваша задача — определить длину листов, из которых изготовят стенгазету, а также выяснить, какова будет суммарная длина отрезанных частей.
Первая строка — целые числа N и M через пробел (1 ≤ N ≤ 105, 1 ≤ M ≤ N).
Вторая строка — целые числа Li, i = 1, 2, ..., N (1 ≤ Li ≤ 1000) через пробел — длины соответствующих листов.
В первой строке выведите два целых числа через пробел — длину листов, из которых будет изготовлена стенгазета, и суммарную длину отрезанного.
Пример 1
Входные данные
5 3
25 1 4 9 16
1 11
Входные данные
8 4
3 2 9 2 7 2 1 1
2 1