Problem description

Każdy wie (może Ci młodsi już nie pamiętają) jak działa klawiatura standardowego telefonu komórkowego. Klawisze z cyframi mają przypisane po kilka liter (przy czym litery są przypisywane do kolejnych klawiszy zgodnie z kolejnością alfabetyczną spójnymi przedziałami). Na przykład do klawisza 2 przypisano litery abc. Aby uzyskać literę b należy nacisnąć klawisz 2 dwukrotnie.

Sprawa wydaje się łatwa, niestety przechodzimy do Bajtocji. Klawiatury telefonów komórkowych mają tam dokładnie N klawiszy, a alfabet liczy sobie K znaków (pomiędzy którymi także istnieje jakiś porządek). Twoim zadaniem będzie zaprojektować, które klawisze zostaną przypisane do których klawiszy. Oczywiście nadal należy przydzielać klawisze spójnymi przedziałami liter z bajtockiego alfabetu.

Przydziału należy dokonać tak, aby Bajtoczanom żyło się lepiej (nie kojarzyć z hasłem wyborczym pewnej partii), czyli aby zminimalizować liczbę przyciśnięć klawiszy przez Bajtoczan. Znane są częstości występowań liter we wszystkich obecnie istniejących bajtockich tekstach źródłowych. Celem jest przygotowanie takiego przypisania klawiszy, aby liczba przyciśnięć klawiszy potrzebna na ich wprowadzenie była jak najmniejsza (zakładamy więc, że język Bajtocji będzie ewoluował stosunkowo wolno).

Napisz program, który: wczyta liczbę dostępnych klawiszy na klawiaturze bajtockiego telefonu komórkowego oraz częstości wystąpień poszczególnych liter w bajtockich tekstach, wyznaczy optymalny układ klawiatury telefonu komórkowego i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i K, oddzielone pojedynczym odstępem i określające kolejno liczbę klawiszy na klawiaturze bajtockiego telefonu oraz liczbę znaków w bajtockim alfabecie.

W drugim (i ostatnim) wierszu wejścia znajduje się K liczb T_i, pooddzielanych pojedynczymi odstępami. i-ta liczba określa liczbę wystąpień i-tej litery alfabetu (według porządku występowania liter w alfabecie Bajtocji) we wszystkich zbadanych tekstach źródłowych.

Wyjście

Twój program powinien wypisać na wyjście dokładnie dwa wiersze. W pierwszym z nich powinna się znaleźć jedna liczba całkowita – minimalna łączna liczba przyciśnięć klawiszy, aby wprowadzić wszystkie teksty źródłowe. W drugim wierszu powinno się znaleźć N pooddzielanych liczb całkowitych R_i. i-ta liczba powinna określać ile kolejnych liter przypisano klawiszowi numer i w znalezionym rozwiązaniu.

Jeśli istnieje wiele możliwych rozwiązań – należy wypisać takie w którym R_n jest możliwie największe, a jeśli to nie rozstrzyga to należy porównywać według R_n − 1, R_n − 2, itd. aż do uzyskania rozstrzygnięcia.

Ograniczenia

1 ≤ N ≤ 200, 1 ≤ K ≤ 40 000, 1 ≤ T_i ≤ 10⁷.

W testach wartych łącznie 50% maksymalnej punktacji: N ≤ 50, K ≤ 4 000.

Przykład

3 6
10 5 2 10 2 6

46
3 2 1