P11100 [ROI 2022] 交换 (Day 2)

翻译自 [ROI 2022 D2T1](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-roi-2022-day2.pdf)。 给定一个 $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$，并且可能包含前导零。

| Subtask | 分值 | $n\le$ | $y\le$ | 特殊性质 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $27$ | $9$ | $10^8$ | | | $2$ | $13$ | $20$ | $10^8$ | | | $3$ | $19$ | $10^5$ | $1$ | | | $4$ | $25$ | $10^5$ | $10^8$ | $x$ 由 `1` 或 `2` 组成 | | $5$ | $8$ | $10^5$ | $10^8$ | | | $6$ | $8$ | $10^5$ | $10^{16}$ | |