P11100 [ROI 2022] Swap (Day 2)

Translated from [ROI 2022 D2T1](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-roi-2022-day2.pdf)。 You are given an $n$-digit decimal number $x$。You may swap two adjacent digits any number of times, and each swap costs $y$。If after $k$ such swaps you obtain the number $x_{new}$, then the profit equals $x_{new} - k \times y$。 Definition: if by swapping you obtain a number $x_{new}$ from $x$, and during this process you achieve the maximum possible profit, then $x_{new}$ is called an optimal number。 For example, when $y = 114$, you can move the digit $7$ in $3327$ to the front by swapping $3$ times, obtaining the maximum profit $7332 - 3 \times 114 = 6990$。In this case, $7332$ is called an optimal number。

As is well known, such optimal numbers may be more than one (for the same $x$, all its optimal numbers have the same profit, but their values are different)。Given $x$ and $y$, you need to determine the maximum value among all optimal numbers。

The first line contains an integer $x$ consisting of $n$ decimal digits ($1 \le n \le 10^5$)。The number $x$ may have leading zeros。 The second line contains an integer $y$, the cost of one swap ($1 \le y \le 10^{16}$)。

Output an integer $x_{new}$, the maximum among all optimal numbers。The length of $x_{new}$ is $n$, and it may contain leading zeros。

| Subtask | Score | $n \le$ | $y \le$ | Special property | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $27$ | $9$ | $10^8$ | | | $2$ | $13$ | $20$ | $10^8$ | | | $3$ | $19$ | $10^5$ | $1$ | | | $4$ | $25$ | $10^5$ | $10^8$ | $x$ consists of `1` or `2` | | $5$ | $8$ | $10^5$ | $10^8$ | | | $6$ | $8$ | $10^5$ | $10^{16}$ | | Translated by ChatGPT 5