问题2705--仓鼠更有精神

2705: 仓鼠更有精神

时间限制: 2 Sec  内存限制: 32 MB
提交: 79  解决: 10
[状态] [讨论版] [提交] [命题人:]
题目描述

注:本题为C题“仓鼠很有精神”的升级版,请确保自己理解音量值机制再开此题。

现在,又有一排n名小仓鼠面对高年级大仓鼠,开始做自我介绍。每只鼠的自我介绍一开始都是固定的一个字符串。这次,为了让自己的自我介绍显得更有精神,仓鼠们可以对自己的自我介绍进行修改,具体方式是将其中任意一个字母改成自己想要的字母。但是每只仓鼠的口才不尽相同,所以能修改的字母数量也不尽相同。现在,大仓鼠希望你能告诉他,每只小仓鼠的自我介绍能达到的最大的音量值是多少。

输入

第一行会给出一个整数n

接下来的n行,每行会有一个以小写字母组成的字符串si和一个整数ki,分别表示这只仓鼠的自我介绍,以及这只仓鼠的口才能修改的字母总数。1si106,0kisi

我们保证所有小仓鼠的自我介绍的长度之和不超过5×106,即si5×106

请注意,本题的背景与C题有关联,但数据范围与C题不同。

输出

对于每一只仓鼠,你需要输出一行一个整数,表示答案。



样例输入 Copy
3
henyoujingshen 0
henyoujingshen 1
henyoujingshen 3
样例输出 Copy
2
4
7
提示

k=1: henyoujingshen => henyouuingshen

k=3: henyoujingshen => heeeouuingshen