最大子字符串开销

题目描述

给定一个字符串 $s$，一个由互不相同的小写字母组成的字符串 chars，以及一个与 chars 等长的整数数组 vals。定义每个字符的价值如下：

• 若字符不在 chars 中，价值为它在字母表中的位置（a 为 1，b 为 2，…，z 为 26）。
• 若字符在 chars 中，且位置为 $i$（从 0 开始），则价值为 vals[i]。

子字符串的开销是该子字符串中所有字符价值的总和。空字符串的开销为 0。

请你返回字符串 $s$ 的所有子字符串中，开销的最大值。

输入格式

第一行包含字符串 $s$（$1 \leq |s| \leq 10^5$），仅由小写英文字母组成。
第二行包含字符串 chars（$1 \leq |chars| \leq 26$），其中字符互不相同，仅由小写字母组成。
第三行包含 $|chars|$ 个整数 vals[i]（$-1000 \leq vals[i] \leq 1000$），以空格分隔。

输出格式

输出一个整数，表示所有子字符串中的最大开销。

示例

示例 1

输入：

adaa
d
-1000

输出：

2

解释：
字符 a 价值为 1，d 价值为 -1000。最大开销子字符串为 "aa"，开销 $1 + 1 = 2$。

示例 2

输入：

abc
abc
-1 -1 -1

输出：

0

解释：
任何非空子字符串开销均为负数，选空字符串开销 0 为最大。

数据范围

• $1 \leq |s| \leq 10^5$
• $1 \leq |chars| \leq 26$
• vals.length = |chars|
• $-1000 \leq vals[i] \leq 1000$