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 ≤ 100000
• 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.

#include <bits/stdc++.h>


using namespace std;

ifstream cin("cifre5.in");
ofstream cout("cifre5.out");

int n , v[100001] , ok , d , poz , poz2 , sum , i2 , k , A[10001] , cnt;

int main()
{
    cin >> n >> k;
    for(int i = 1 ; i <= n ; i++)
        cin >> v[i];
    sort(v + 1, v + n + 1);
    while(v[poz] == 0) poz++;
    if(poz == 1) poz -= k;
    poz += k - 1;
    poz2 = n; d = -1;
    i2 = 1;
    while (sum > 0 || i2 <= n)
    {
        for(int i = 1 ; i <= k && i2 <= n ; i++)
        {
            if(poz2 == poz && ok == 0 ) d = 1 , poz2 = 1 , ok = 1;
            else if (poz2 == poz - k + 1 && ok == 1) d = -1 , poz2 = poz , ok = 2;
            sum += v[poz2];
            poz2 += d;
            i2++;
        }
        A[++cnt] = sum % 10;
        sum /= 10;
    }
    for(int i = cnt ; i >= 1 ; i--)
        cout << A[i];
    return 0;
}