시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 161 51 43 33.858%

문제

수열이 주어졌을 때, M을 수열의 모든 두 원소의 차이 중 가장 큰 값이라고 한다. m은 그 차이 중 가장 작은 값이라고 한다.

크기가 N인 수열 V가 주어진다. 여기서 K개 수를 적절히 제거해서 M+m을 가능한 작게 만드는 프로그램을 작성하시오.

입력

첫째 줄에 N(3 ≤ N ≤ 1,000,000)과 K(1 ≤ K ≤ N-2)가 주어진다.

둘째 줄에 V의 원소가 공백으로 구분되어 주어진다. (-5,000,000 ≤ Vi ≤ 5,000,000)

출력

첫째 줄에 가장 작은 M+m을 출력한다.

예제 입력 1

5 2
-3 -2 3 8 6

예제 출력 1

7
W3sicHJvYmxlbV9pZCI6IjM5ODgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMTggXHVhY2UwXHViOTc0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiJcclxuPHA+XHJcblx0XHVjMjE4XHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIE1cdWM3NDQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWI0NTAgXHVjNmQwXHVjMThjXHVjNzU4IFx1Y2MyOFx1Yzc3NCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFjMTJcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBtXHVjNzQwIFx1YWRmOCBcdWNjMjhcdWM3NzQgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVhYzEyXHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVkMDZjXHVhZTMwXHVhYzAwIE5cdWM3NzggXHVjMjE4XHVjNWY0IFZcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM1ZWNcdWFlMzBcdWMxMWMgS1x1YWMxYyBcdWMyMThcdWI5N2MgXHVjODAxXHVjODA4XHVkNzg4IFx1YzgxY1x1YWM3MFx1ZDU3NFx1YzExYyBNK21cdWM3NDQgXHVhYzAwXHViMmE1XHVkNTVjIFx1Yzc5MVx1YWM4YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTigzICZsZTsgTiAmbGU7IDEsMDAwLDAwMClcdWFjZmMgSygxICZsZTsgSyAmbGU7IE4tMilcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwIFZcdWM3NTggXHVjNmQwXHVjMThjXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoLTUsMDAwLDAwMCAmbGU7IFY8c3ViPmk8XC9zdWI+ICZsZTsgNSwwMDAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBNK21cdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM5ODgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSQVpMSUtBIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyYjMzk7cyBuZXdlc3QgbWF0aCBob21ld29yayBhc3NpZ25tZW50IGlzIGEgdmVyeSBkaWZmaWN1bHQgb25lISBHaXZlbiBhIHNlcXVlbmNlLCBWLCBvZiBOIGludGVnZXJzLCByZW1vdmUgZXhhY3RseSBLIG9mIHRoZW0gZnJvbSB0aGUgc2VxdWVuY2UuIExldCBNIGJlIHRoZSBsYXJnZXN0IGRpZmZlcmVuY2Ugb2YgYW55IHR3byByZW1haW5pbmcgbnVtYmVycyBpbiB0aGUgc2VxdWVuY2UsIGFuZCBtIHRoZSBzbWFsbGVzdCBzdWNoIGRpZmZlcmVuY2UuIFNlbGVjdCB0aGUgSyBpbnRlZ2VycyB0byBiZSByZW1vdmVkIGZyb20gViBpbiBzdWNoIGEgd2F5IHRoYXQgdGhlIHN1bSBNICsgbSBpcyB0aGUgc21hbGxlc3QgcG9zc2libGUuIE1pcmtvIGlzbiYjMzk7dCB2ZXJ5IGdvb2QgYXQgbWF0aCwgc28gaGUgaGFzIGFza2VkIHlvdSB0byBoZWxwIGhpbSEmbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBwb3NpdGl2ZSBpbnRlZ2VycywgTiAoMyAmbGU7IE4gJmxlOyAxIDAwMCAwMDApIGFuZCBLICgxICZsZTsgSyAmbGU7IE4gLSAyKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIE4gc3BhY2Utc2VwYXJhdGVkIHBvc2l0aXZlIGludGVnZXJzICZuZGFzaDsgdGhlIHNlcXVlbmNlIFYgKC01IDAwMCAwMDAgJmxlOyBWPHN1Yj5pPFwvc3ViPiAmbGU7IDUgMDAwIDAwMCkuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgc21hbGxlc3QgcG9zc2libGUgc3VtIE0gKyBtLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=