Rezolvare PBinfo #684

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ța

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 cifre5.in conţine pe prima linie două valori naturale n şi k cu semnificaţia de mai sus. Pe a doua linie fişierul conţine n cifre separate prin câte un spaţiu.

Date de ieșire

Fişierul cifre5.out va conţine pe prima linie un singur număr care va reprezenta suma celor k numere construite.

Restricții și precizări

• 2 ≤ n ≤ 100.000
• 1 ≤ k ≤ 100
• k ≤ n
• cel puţin k cifre dintre cele n sunt nenule

Exemplu:

cifre5.in

7 3
2 1 0 4 9 9 1

cifre5.out

152

Explicație

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ă construim numerele 19, 24 şi 109. Există şi alte posibilităţi de a construi cele trei numere.