Razlika - COCI
Mirko's newest math homework assignment is a very difficult one! Given a sequence, V, of N integers, remove exactly K of them from the sequence. Let M be the largest difference of any two remaining numbers in the sequence, and m the smallest such difference. Select the K integers to be removed from V in such a way that the sum M + m is the smallest possible. Mirko isn't very good at math, so he has asked you to help him!
InputThe first line of input contains two positive integers, N (3 ≤ N ≤ 1 000 000) and K (1 ≤ K ≤ N - 2). The second line of input contains N space-separated positive integers – the sequence V (-5 000 000 ≤ Vi ≤ 5 000 000).
OutputThe first and only line of output must contain the smallest possible sum M + m.
Input:
Output:
Input:
Output:
Input:
Output:
5 2
-3 -2 3 8 6Output:
7Input:
6 2
-5 8 10 1 13 -1Output:
13Input:
6 3
10 2 8 17 2 17Output:
6Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.