题目描述
注：本题为C题“仓鼠很有精神”的升级版，请确保自己理解“音量值”机制再开此题。
现在，又有一排n名小仓鼠面对高年级大仓鼠，开始做自我介绍。每只鼠的自我介绍一开始都是固定的一个字符串。这次，为了让自己的自我介绍显得更有精神，仓鼠们可以对自己的自我介绍进行修改，具体方式是将其中任意一个字母改成自己想要的字母。但是每只仓鼠的口才不尽相同，所以能修改的字母数量也不尽相同。现在，大仓鼠希望你能告诉他，每只小仓鼠的自我介绍能达到的最大的音量值是多少。
输入
第一行会给出一个整数n
接下来的n行，每行会有一个以小写字母组成的字符串si和一个整数ki，分别表示这只仓鼠的自我介绍，以及这只仓鼠的口才能修改的字母总数。1≤si≤106,0≤ki≤si
我们保证所有小仓鼠的自我介绍的长度之和不超过5×106，即∑si≤5×106
。
请注意，本题的背景与C题有关联，但数据范围与C题不同。
输出
对于每一只仓鼠，你需要输出一行一个整数，表示答案。
样例输入
Copy
3
henyoujingshen 0
henyoujingshen 1
henyoujingshen 3
样例输出 Copy
2
4
7
提示
k=1: henyoujingshen
=> henyouuingshen
k=3: henyoujingshen
=> heeeouuingshen
来源/分类