Максимизация выигрыша

Дано целое неотрицательное число $x$, состоящее из $n$ десятичных цифр. В нём можно произвольное число раз поменять местами две соседние цифры. За каждый обмен начисляется штраф равный $y$. После выполнения обменов начисляется бонус, равный получившемуся из $x$ числу $x\_{new}$. Таким образом, если в результате $k$ обменов получено число $x\_{new}$, выигрыш равен $x\_{new} - ky$.

Будем называть число $x\_{new}$ оптимальным, если его можно получить из $x$ в результате обменов, добившись при этом максимального возможного выигрыша.

По заданным $x$ и $y$ определите наибольшее среди оптимальных чисел.

В первой строке дано одно целое число $x$, состоящее из $n$ десятичных цифр ($1 \le n \le 100\\,000$). Число $x$ может иметь ведущие нули.

Во второй строке дано одно целое число $y$ --- штраф за один обмен цифр ($1 \le y \le 10^{16}$).

Выведите единственное целое число $x\_{new}$ --- наибольшее среди оптимальных чисел. Число $x\_{new}$ должно иметь длину $n$ и может содержать ведущие нули.

В первом примере после обмена цифр $1$ и $7$ получается число $710$, выигрыш равен $710-15=695$.

Во втором примере менять цифры местами не выгодно, если оставить число как есть, выигрыш равен $170$, а если поменять, то выигрыш будет равен $710-600=110 < 170$.