带权共通旋律

题目描述

两段旋律分别记为字符串 $A$ 与 $B$（仅包含小写字母）。每个字母都有一个音色权值 $w[c]$。从两段旋律中选出一个公共子序列，其“价值”为所选字符权值之和。

请你计算最大可能价值。

输入格式

输入共三行。

• 第一行是字符串 $A$。
• 第二行是字符串 $B$。
• 第三行包含 26 个整数，依次表示 a 到 z 的权值。

输出格式

输出一行，一个整数，表示最大可能价值。

输入输出样例 #1

输入 #1

abac
cacb
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

输出 #1

4

样例解释 #1

一种最优公共子序列是 ab，价值为 $1+2=3$； 但 ac 价值为 $1+3=4$ 更大，因此答案为 $4$。

数据范围

对于所有测试数据，保证：

• $1 \le |A|,|B| \le 2000$；
• 权值为非负整数，且不超过 $10^6$。