C-牛牛组数_牛客编程巅峰赛S2第1场

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

现在有一个长度为n的只包含数字1-9的字符串x，用这n个数字组成k个数。这k个数每个数至少要用字符串x中的一个数字，字符串x中的每个位置的字符要在这k个数中出现一次。求这k个数的和最大是多少。

组成数字的定义如下：

比如n=3的字符串x为“121”

如果k=3，那么组成k个数只有{1,1,2}这一种可能,和只有一种可能为4

如果k=2，那么组成k个数的方案有{11,2},{12,1},{21,1}三种可能，和最大为21+1=22

如果k=1，那么组成k个数的方案有{112},{121},{211}三种可能，和最大为211

示例1

复制

"345",2

复制

"57"

53+4=57，无法得到比57更大的和

示例2

复制

"233333",3

复制

"3338"

3332+3+3=3338，无法得到比3338更大的和

示例3

复制

"111222333444555666777888999",1

复制

"999888777666555444333222111"

无法得到比999888777666555444333222111更大的和

对于百分之20的数据: $1 \leq n \leq 5;1 \leq k \leq n;$

对于百分之50的数据: $1 \leq n \leq 5000;1 \leq k \leq n;$

对于百分之100的数据: $1 \leq n \leq 100\,000;1 \leq k \leq n;$

(注意给的字符串和返回的字符串都不带引号)