Krzysztof Diks, Marcin Kubica
Tłumaczenie

Post Office

Wzdłuż prostoliniowej autostrady znajduje się wiele miast. Na autostradę można patrzeć jak na oś całkowitoliczbową. Miasta znajdują się w pewnych punktach na tej osi (o całkowitych współrzędnych) i różne miasta znajdują się w różnych punktach Odległóść między miastami definiuje się jako wartość bezwzględną z różnicy ich współrzędnych.

W miastach, niekoniecznie wszystkich, postanowiono wybudować urzędy pocztowe - w każdym mieście co najwyżej jeden. Należy znaleźć dla nich miejsce budowy w taki sposób, żeby zminimalizować sumę odległości miast od ich najbliższych urzędów pocztowych.

Napisz program, który mając dane położenie miast i liczbę planowanych urzędów pocztowych, obliczy najmniejszą możliwą sumę odległości miast od ich najbliższych urzędów pocztowych oraz odpowiadający tej sumie sposób usytuowania tych urzędów.

Wejście

Nazwą pliku wejściowego jest POST.IN. Pierwszy wiersz zawiera dwie liczby całkowite: pierwszą z nich jest liczba miast V, 1le V le 300, a drugą liczba urzędów pocztowych P, 1 le P le 30, P le V. Drugi wiersz zawiera V liczb całkowitych uporządkowanych rosnąco. Te liczby to współrzędne miast. Dla każdej współrzędnej X mamy 1 le X le 10,000.

Wyjście

Nazwą pliku wyjściowego jest POST.OUT. Pierwszy wiersz zawiera jedną liczbę całkowitą S, którą jest suma odległości miast od ich najbliższych urzędów pocztowych. Ich położenia są opisane w następnym wierszu. Drugi wiersz zawiera P liczb całkowitych w porządku rosnącym. Te liczby są współrzędnymi (pozycjami) miast, w których należy wybudować urzędy pocztowe. Może być wiele różnych sposobów lokalizacji urzędów pocztowych, ale Twój program musi podać tylko jeden z nich.

Przykład

POST.IN: 


10 5
1 2 3 6 7 9 11 22 44 50

POST.OUT: 


9
2 7 22 44 50

Częściowa punktacja

Jeśli wynik działania Twojego programu nie jest zgodny z opisem wyjścia otrzymasz 0 punktów. W przeciwnym razie otrzymasz liczbę punktów obliczaną według poniższej tabelki. Jeśli Twój program wypisuje sumę S, a najmniejszą możliwą sumą jest Smin, wówczas liczba punktów jest obliczana jak następuje (q=S/Smin):



cccccccc q=S/Smin & q=1.0 & 1.0<qle 1.1 & 1.1<qle 1.15 & 1.15<qle 1.2

c & 10 & 5 & 4 & 3



cccccccc q=S/Smin & 1.2<qle 1.25 & 1.25<qle 1.3 & 1.3<q

c & 2 & 1 & 0