# [Solution] Not a Cheap String solution codeforces

Not a Cheap String solution codeforces – 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=71+2+3+1=7.

Table of Contents

## [Solution] Not a Cheap String solution codeforces

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.

## [Solution] Not a Cheap String solution codeforces

The first line of input contains an integer 𝑡t (1𝑡1041≤t≤104) — 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 21052⋅105.

The second line contains an integer 𝑝p (1𝑝52000001≤p≤5200000).

It is guaranteed that the sum of string lengths 𝑤w over all test cases does not exceed 21052⋅105.

Output

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.

## [Solution] Not a Cheap String solution codeforces

Example
input

Copy
5
abca
2
abca
6
codeforces
1
codeforces
10
codeforces
100

output

Copy
aa
abc

cdc
codeforces