← 返回题目列表

Codeforces · 1702/D

D. 不是一个便宜的字符串

中文机器翻译题面 查看原题

令 $$$s$$$ 为一串小写拉丁字母。它的价格是其中包含的字母索引(1 到 26 之间的整数)的总和。例如,字符串abca的价格为$$$1+2+3+1=7$$$。

给出字符串 $$$w$$$ 和整数 $$$p$$$。从 $$$w$$$ 中删除最少数量的字母,使其价格小于或等于 $$$p$$$ 并打印结果字符串。请注意,结果字符串可能为空。您可以删除任意字母,它们不必连续出现。如果给定字符串 $$$w$$$ 的价格小于或等于 $$$p$$$,则不需要删除任何内容,并且必须输出 $$$w$$$。

请注意,当您从 $$$w$$$ 中删除字母时,剩余字母的顺序将保留。例如,如果从字符串 test 中删除字母 e,则会得到 tst。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中测试用例的数量。以下是 $$$t$$$ 测试用例的描述。

每个案例由两行组成。

第一个是字符串 $$$w$$$,它非空,由小写拉丁字母组成。其长度不超过$$$2\cdot10^5$$$。

第二行包含一个整数 $$$p$$$ ($$$1 \le p \le 5\,200\,000$$$)。

保证所有测试用例的字符串长度 $$$w$$$ 的总和不超过 $$$2 \cdot 10^5$$$。

输出

准确输出 $$$t$$$ 行,其中第 $$$i$$$ 行应包含第 $$$i$$$ 组输入数据的答案。打印通过删除字母从 $$$w$$$ 获得的最长字符串,使其价格小于或等于 $$$p$$$。如果有多个答案,则输出其中任何一个。

请注意,空字符串 — 是可能的答案之一。在这种情况下,只需输出一个空字符串。

示例

输入 #1

5
abca
2
abca
6
codeforces
1
codeforces
10
codeforces
100

输出 #1

aa
abc

cdc
codeforces