P9190 [USACO23OPEN] Pareidolia G

Pareidolia is the phenomenon where your eyes tend to see familiar patterns in images where none really exist -- for example seeing a face in a cloud. As you might imagine, with Farmer John's constant proximity to cows, he often sees cow-related patterns in everyday objects. For example, if he looks at the string "bqessiyexbesszieb", Farmer John's eyes ignore some of the letters and all he sees is "bessiexbessieb" -- a string that has contains two contiguous substrings equal to "bessie".

### 题目背景 Pareidolia 是一种现象，指的是人们倾向于在并不真正存在的地方看到熟悉的图案——例如在云中看到一张脸。可以想象，由于农夫 John 经常与奶牛接触，他常常在日常物品中看到与奶牛相关的图案。例如，如果他看到字符串 "bqessiyexbesszieb"，农夫 John 的眼睛会忽略其中的一些字母，而他看到的只是 "bessiexbessieb"——一个包含两个连续子串等于 "bessie" 的字符串。 给定一个长度不超过 $2 \cdot 10^5$ 的字符串，且仅由字符 a-z 组成，其中每个字符都有一个相关的删除成本。计算通过删除零个或多个字符后，能够形成的等于 "bessie" 的连续子串的最大数量，以及为了实现这一目标所需删除字符的最小总成本。

第一行包含字符串。第二行包含每个字符的删除成本（一个在 $\left[1,1000\right]$ 范围内的整数）。

输出最大数量的 "bessie" 出现次数，以及实现这一数量所需的最小成本。

对于第一个样例，通过删除位置 4 的 's'，我们可以使整个字符串变为 "bessie"。位置 4 的字符成本为 $4$，因此我们的答案是成本 $4$ 得到 $1$ 个 "bessie"，这是我们可以做到的最佳结果。 对于第二个样例，通过删除位置 5-7 的 "con"，我们可以使字符串变为 "bebessiete"，其中包含中间的 "bessie"。位置 5-7 的字符成本为 $5 + 7 + 9 = 21$，因此我们的答案是成本 $21$ 得到 $1$ 个 "bessie"，这是我们可以做到的最佳结果。 对于第三个样例，通过删除位置 4-10 的 "giraffe"，我们可以使字符串变为 "bessiebessibessie"，其中包含开头和结尾的 "bessie"。"giraffe" 有 7 个字符，且所有字符的成本均为 $1$，因此我们的答案是成本 $7$ 得到 $2$ 个 "bessie"，这是我们可以做到的最佳结果。此样例满足第二个子任务的约束条件。 - 输入 4-5：$N \le 2000$。 - 输入 6-8：所有成本均为 $1$。 - 输入 9-17：没有额外限制。