Background

Translated from ROI 2022 D2T1。

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。

Problem Description

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。

Input Format

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 Format

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

170
15

710

170
600

170

314599
17713

931459

001
1000

001

3327
114

7332

Hint

Translated by ChatGPT 5