그룹에 대한 연구

N개의 정수가 담긴 주머니가 있고, 이 정수들을 M개의 서로 다른 그룹에 넣으려고 한다. 정수를 분배할 때 각 정수는 정확히 하나의 그룹에 속해야 하며, 서로 다른 두 그룹의 크기 차이는 1 이하여야 한다.

그룹의 비용은 그 그룹에 있는 가장 작은 정수와 같고, M개 그룹의 총 비용은 각 그룹의 비용의 합과 같다. 빈 그룹의 비용은 0이다.

이 문제에서 해야 할 일은 주어진 N개의 정수(중복될 수 있다)를 M개의 서로 다른 그룹에 넣어 그룹의 총 비용을 최소로 만드는 방법을 찾는 것이다. 또한 총 비용을 최대로 만드는 방법도 찾아야 한다. 총 비용만 출력한다.

입력의 첫 줄에는 두 정수 N M (1 ≤ N, M ≤ 100000)이 주어지며, 이는 각각 주어진 정수의 개수와 만들어야 하는 그룹의 개수이다. 다음 줄에는 N개의 정수 Ai (0 ≤ Ai ≤ 1000000)가 주어진다.

한 줄에 두 정수를 공백 하나로 구분하여 출력한다. 첫 번째는 최소 총 비용, 두 번째는 최대 총 비용이다.