← 返回题目
题库练习 [COCI-2012_2013-contest4]#5 RAZLIKA
← 上一题 下一题 →

A1269 | [COCI-2012_2013-contest4]#5 RAZLIKA

来源COCI
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

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!

输入格式

The 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).

输出格式

The first and only line of output must contain the smallest possible sum M + m.

输入输出样例

输入 #1
5 2 
-3 -2 3 8 6
输出 #1
7
输入 #2
6 2 
-5 8 10 1 13 -1
输出 #2
13
输入 #3
6 3 
10 2 8 17 2 17
输出 #3
6
C++ 编辑器
输入
输出