A104750.雾港冲刺营的队伍序列

雾港冲刺营的报名处排着长队。工作人员会把所有人的昵称拿去做一次“统一排序”：按昵称的字典序从小到大重新排队。你报名得最晚，所以如果出现同名的人，你一定会排在所有同名者的最后面。

你的昵称是一个长度为 $n$ 的小写字母字符串 $S$。第 $i$ 个位置的“改动单价”为 $p_i$：把该位置的字母降低 $1$ 位（例如 d -> c）需要支付 $p_i$ 枚代币。你只能把字母变小，不能变大。

更具体地，把第 $i$ 位从字符 x 改成字符 y（$y\le x$，其中 $a=0,b=1,\dots,z=25$），需要支付

$$((x-y)\times p_i)$$

枚代币。

不过实验室对你有两条限制：

• 你最多只能修改 $K$ 个不同的位置（同一个位置无论降低多少位，都只算修改了 $1$ 个位置）；
• 你总花费不超过 $B$ 枚代币。

队伍里除了你以外还有 $m$ 个人，他们的昵称各不相同也可能相同（长度不一定相同）。重排规则为：

1. 先按昵称字典序从小到大排序；
2. 若昵称完全相同，则按报名先后排序；你报名最晚，因此同名时你排在最后。

字典序比较按通常字符串比较：从左到右找第一处不同字符，较小者更小；若一方是另一方的前缀，则较短的字符串更小。

请你在限制内修改自己的昵称，使得你在重排后的队伍中名次（从 $1$ 开始）尽可能小，并输出这个最小名次与对应的最终昵称。若能达到最小名次的方案不唯一，输出其中字典序最小的最终昵称。

第一行四个整数 $n,m,K,B$。

第二行一个长度为 $n$ 的字符串 $S$（只含小写字母）。

接下来 $m$ 行，每行一个字符串，表示其他人的昵称（只含小写字母，长度任意）。

最后一行 $n$ 个整数 $p_1,p_2,\dots,p_n$。

第一行输出一个整数，表示你能达到的最小名次。

第二行输出一个字符串，表示达到该名次的最终昵称（若有多种，输出字典序最小的）。

样例解释

你可以把 candy 改成 aamdy。例如第 $1$ 位 c->a 降低 $2$ 位，花费 $2\times3=6$；第 $3$ 位 n->m 降低 $1$ 位，花费 $1\times4=4$。此时共修改了 $2$ 个位置、总花费 $10$，满足限制。队伍里已经有人昵称为 aamdy，同名时你报名最晚，所以你排在他后面，名次为 $2$。可以验证在限制内不可能得到名次 $1$，因此答案是 $2$。

---

数据范围

• $0\le K\le n$
• $0\le B\le 10^{18}$
• $1\le p_i\le 10^{9}$
• 其他人的昵称只包含小写字母

测试点编号	$n$ 上界
$1\sim4$	$n\le 20$
$5\sim10$	$n\le 10000$
$11\sim20$	$n\le 200000$