OIG XVI - naj

// https://szkopul.edu.pl/problemset/problem/STjOFeUHMP1RSUi81siSWe7O/site/?key=statement
// OIG XVI (2 etap)

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

std::map<int, int> m;

long long pot(long long a, long long b) {
    if (b == 1) return a;
    if (a == 0) return 0;
    if (b == 0) return 1;
    if (b % 2 == 1)
        return (a * pot(a, b - 1));
    else {
        long long c = pot(a, b / 2);
        return (c * c);
    }
}

int min_av(bool include_zero = true) {
    int ans = 0;

    for (int i = !include_zero; i <= 9; i++) {
        if (m[i] > 0) {
            m[i]--;
            ans = i;
            break;
        }
    }

    return ans;
}

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    std::string s;
    std::cin >> s;

    for (const auto& c : s) {
        m[c - '0']++;
    }

    int k;
    std::cin >> k;

    long long suma = 0;
    int n = s.size();

    int asz = n / k, add = n % k;

    for (int i = 1; i <= 9; i++) {
        if (m[i] <= add) {
            suma += i * m[i] * pot(10, asz);
            add -= m[i];
            m[i] = 0;
        } else if (m[i] > add) {
            suma += i * add * pot(10, asz);
            m[i] -= add;
            add = 0;
            break;
        }
    }

    add = n % k;

    for (int i = 0; i < asz; i++) {
        for (int j = 0; j < k; j++) {
            bool flag = true;

            if (i == 0 && (j >= add || add == 0)) {
                flag = false;
            }

            auto temp = min_av(flag) * pot(10, asz - i - 1);
            suma += temp;
        }
    }

    std::cout << suma << '\n';

    return 0;
}