题目背景

翻译自 ROI 2022 D2T1。

给定一个 $n$ 位十进制数 $x$。可以任意多次交换相邻的两个数位，每次交换会产生一个代价 $y$。如果通过 $k$ 次这样的交换得到了数字 $x_{new}$，则收益等于 $x_{new}-k\times y$。

定义：如果通过交换从 $x$ 得到了数字 $x_{new}$，并且在此过程中达到了最大可能的收益，则称数字 $x_{new}$ 为最优数字。

例如，当 $y=114$ 时，可以通过交换 $3$ 次将数字 $3327$ 中的 $7$ 移到最前面，得到最大的收益 $7332-3\times114=6990$。此时就称 $7332$ 为最优数字。

题目描述

众所周知，这样的最优数字可能不止一个（对于同一个 $x$，它的所有最优数字获得的收益是相等的，但它们的值不相等）。对于给定的 $x$ 和 $y$，需要确定最优数字中的最大值。

输入格式

第一行包含一个由 $n$ 个十进制数位组成的整数 $x$（$1\le n\le10^5$），数字 $x$ 可能有前导零。

第二行包含一个整数 $y$，表示一次交换的代价（$1\le y\le10^{16}$）。

输出格式

输出一个整数 $x_{new}$，表示最优数字中的最大值。数字 $x_{new}$ 的长度为 $n$，并且可能包含前导零。

170
15

710

170
600

170

314599
17713

931459

001
1000

001

3327
114

7332

提示