სხვაობათა ჯამი

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: COCI, 2012/13, #4


მოცემულია N მთელი რიცხვისაგან შედგენილი V მიმდევრობა. წაშალეთ ამ მიმდევრობიდან ზუსტად K რიცხვი. ვთქვათ, M არის უდიდესი სხვაობა დარჩენილი რიცხვების ყველა შესაძლო წყვილს შორის, ხოლო m არის უმცირესი სხვაობა ყველა შესაძლო წყვილს შორის. შეარჩიეთ წასაშლელი K რიცხვი ისე, რომ ჯამი M+m იყოს მინიმალური.

შესატანი მონაცემები: პირველ სტრიქონში ორი მთელი დადებითი რიცხვი N (3 ≤ N ≤ 1 000 000) და K (1 ≤ K ≤ N - 2). მეორე სტრიქონში N მთელი რიცხვი V მიმდევრობა (-5 000 000 ≤ Vi ≤ 5 000 000).

გამოსატანი მონაცემები: უმცირესი ჯამი M + m.  

 




მაგალითები

შესატანი მონაცემები
5 2 -3 -2 3 8 6 დაკოპირება
გამოსატანი მონაცემები
7 დაკოპირება
შესატანი მონაცემები
6 2 -5 8 10 1 13 -1 დაკოპირება
გამოსატანი მონაცემები
13 დაკოპირება
შესატანი მონაცემები
6 3 10 2 8 17 2 17 დაკოპირება
გამოსატანი მონაცემები
6 დაკოპირება