A15224 | Not a Cheap String

Let $s$ be a string of lowercase Latin letters. Its price is the sum of the indices of letters (an integer between 1 and 26) that are included in it. For example, the price of the string abca is $1+2+3+1=7$ .

The string $w$ and the integer $p$ are given. Remove the minimal number of letters from $w$ so that its price becomes less than or equal to $p$ and print the resulting string. Note that the resulting string may be empty. You can delete arbitrary letters, they do not have to go in a row. If the price of a given string $w$ is less than or equal to $p$ , then nothing needs to be deleted and $w$ must be output.

Note that when you delete a letter from $w$ , the order of the remaining letters is preserved. For example, if you delete the letter e from the string test, you get tst.

The first line of input contains an integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases in the test. The following are descriptions of $t$ test cases.

Each case consists of two lines.

The first of them is the string $w$ , it is non-empty and consists of lowercase Latin letters. Its length does not exceed $2\cdot10^5$ .

The second line contains an integer $p$ ( $1 \le p \le 5\,200\,000$ ).

It is guaranteed that the sum of string lengths $w$ over all test cases does not exceed $2 \cdot 10^5$ .

Output exactly $t$ rows, the $i$ -th of them should contain the answer to the $i$ -th set of input data. Print the longest string that is obtained from $w$ by deleting letters such that its price is less or equal to $p$ . If there are several answers, then output any of them.

Note that the empty string — is one of the possible answers. In this case, just output an empty string.