Largest Lexicographical String by Swaps

Given a string S consisting of lowercase letters and an integer K, your task is to obtain the lexicographically largest string possible by performing at most K swaps. In each swap, you can choose any two characters in the string and exchange them. The lexicographical order is determined as usual (i.e. dictionary order based on the standard order of English letters).

The problem can be formally stated as: Given a string \( S \) and an integer \( K \), find the string \( S' \) such that \( S' \) is the largest possible string (in lexicographical order) obtainable by at most \( K \) swaps of any two characters in \( S \).

Note: If no swap can improve the string, simply output the original string.

inputFormat

The input consists of two lines:

1. The first line contains the string S (only lowercase letters, with length at most 1000).
2. The second line contains the integer K representing the maximum number of swaps allowed.

outputFormat

Output a single line containing the lexicographically largest string that can be obtained from S after performing at most K swaps.

abdc
1

dbac