k_torke
Đurica has written n numbers on the board. As you know, he often likes to play with the written numbers and examine different features of the arrays, and then he gives you to solve that problems. Believe it or not,neither this time is any different. This time, he is asking you to find subset which contains k numbers, among these n numbers, so that the sum of the absolute differences of all pairs of the subset with k numbers is the smallest of the same sums of the other sets with k numbers. In case of tie, he wants you to find the set where the sum of numbers in the set is the maximal.
InputIn the first line of the standard input you will be given integers n (1 <= n <= 100.000) and k (1 <= k <= n), which represent how many numbers were written on the board and the above explained number k, respectively. In the next line are n integers from the interval [1, 1.000.000], space-separated, which represent the numbers written on the board.
OutputOutput two numbers space-separated which represent the sum of the absolute differences of the pairs of numbers of the requested set with k numbers and the sum of the numbers of the requested set.
Input:
Output:
Explanation:
Two sets with 3 numbers have a sum of absolute differences equal to 6.Those sets are {6, 8, 5} and {18, 15, 17}. As the sum of the numbers in the first set is smaller than the sum in the second set, we choose the second set as a solution.
10 3
90 1 18 6 10 8 15 5 17 27Output:
6 50Explanation:
Two sets with 3 numbers have a sum of absolute differences equal to 6.Those sets are {6, 8, 5} and {18, 15, 17}. As the sum of the numbers in the first set is smaller than the sum in the second set, we choose the second set as a solution.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.