Finding a string with enough inversions

For a string $S$ of length $N$, the number of inversions in $S$ is the number of pairs $(i, j)$ with $0 \le i < j < N$ and $S[i] > S[j]$. The first character of a string is character 0. For example, "abcab" has three inversions: $(1, 3)$, $(2, 3)$, $(2, 4)$.

You are given integers $N$ and $V$ and a string $S$. Consider the strings of length $N$ that use each of the first $N$ lowercase letters exactly once, that is, the permutations of those $N$ letters. Call such a string $R$ when it meets both conditions below.

• The number of inversions in $R$ is at least $V$.
• $R$ does not come before $S$ in lexicographic order.

Find the $R$ that comes first in lexicographic order.

The first line contains $N$ ($1 \le N \le 20$).

The second line contains $V$ ($0 \le V \le N \times (N-1) / 2$).

The third line contains the string $S$. $S$ is made of some of the first $N$ lowercase letters, and no letter appears twice. The length of $S$ is at least 1 and at most $N$.

Print an $R$ that meets the conditions on the first line. If no such $R$ exists, print -1.