第 2 题 最小和 (najmniejszasuma)

时间限制 0.5 s · 空间限制 256 MB · 2 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 najmniejszasuma.in，输出文件 najmniejszasuma.out。

XVI OIJ（波兰信息学奥赛 J 组）— 第二阶段

• 时间限制：0.5 秒（C++）/ 6 秒（Python）
• 内存限制：256 MB

题目描述

Bitosia 有一些小牌子，每块牌子上写着一个 0 到 9 的数字。Bitosia 想用这些牌子拼出恰好 $K$ 个正数，使它们的和尽可能小。你能帮她吗？

Bitosia 不允许构造带前导零的数（数开头多余的零）。例如，即使她手上有牌子 0, 3, 9，数 039 也不被允许（但她可以拼出 903 之类）。由于数必须是正的，Bitosia 也不能拼出数 0。

编写程序：读入可用牌子的描述与 $K$，求出可能的最小和。

输入格式

• 第一行包含一个不含空格的非空数字串，长度不超过 200 000。这是 Bitosia 牌子上写的数字。
• 第二行（也是最后一行）包含一个正整数 $K$，表示 Bitosia 想得到（并随后求和）的数的个数。$K$ 不超过可用牌子的数量。

输出格式

输出一个整数——可能的最小和。

可以假设输入数据保证解存在，并且结果不超过 $10^{18}$。

样例

样例 1（naj0a）

输入：

43091372
3

输出：

380

解释：最小和 380 可以通过拼出 107、39 和 234 得到（也存在其他方案）。

样例 2（naj0b）

输入：

4567654
7

输出：

37

样例 3（naj0c）

输入：

615952
3

输出：

100

样例 4（naj0d）

输入：

987654321
3

输出：

774

其他样例

• naj0e：有 200 000 块牌子，每块都是数字 9，$K = 15\,000$。
• naj0f：11100000 重复 25 000 次，$K = 60\,000$。

数据范围与评分

你可以用几种更简单的变体来解决本题——某些测试组满足额外的限制。下表给出了当你的程序通过这些限制的测试时所能获得的分值（满分 100）。