Se dau n cifre. Cu acestea trebuie să formăm k numere astfel încât suma acestor k numere să fie minimă. Singura condiţie pe care trebuie să o respectăm în formarea celor k numere este ca cifrele nule să nu se afle la începutul unui număr.
Cerinţă
Determinaţi suma minimă care se poate obţine prin construirea a k numere care să utilizeze toate cele n cifre.
Date de intrare
Fişierul cifre4.in conţine pe prima linie o două valori naturale n şi k cu semnificaţia de mai sus. Pe a doua linie fişierul conţine n cifre separate printr-un spaţiu.
Date de ieşire
Fişierul cifre4.out va conţine pe prima linie un singur număr care va reprezenta suma celor k numere construite.
Restricţii
• 2 ≤ n ≤ 100000
• 1 ≤ k ≤ 100
• k ≤ n
• cel puţin k cifre dintre cele n sunt nenule
Exemple
cifre4.in
cifre4.out
Explicaţii
7 3
2 1 0 4 9 9 1
152
Cu cele 7 cifre trebuie să formăm 3 numere. Suma minimă care putem să o obţinem este 152 şi poate fi obţinută dacă consturim numerele 19,24 şi 109. Există şi alte posibilităţi de a construi cele trei numere.