题目描述

小A有一个由n个小写字母组成的字符串s，他希望将s划分为若干个子串，使得每个子串中每个字母至多出现一次。 例如，对于字符串street来说，str+e+e+t是满足条件的划分；而s+tree+t不是，因为子串tree中e出现了两次。 额外地，小A给出了价值a₁,a₂,…,aₙ，表示划分后长度为i的子串价值为aᵢ。小A希望最大化划分后得到的子串价值之和。 你能帮他求出划分后子串价值之和的最大值吗？

输入格式

1. 第一行：一个正整数n，表示字符串长度。
2. 第二行：一个包含n个小写字母的字符串s。
3. 第三行：n个正整数a₁,a₂,…,aₙ，表示不同长度的子串价值。

   输出格式

   一行，一个整数，表示划分后子串价值之和的最大值。

   输入样例1

   6
   street
   2 1 7 4 3 3

   输出样例1

   13

   输入样例2

   8
   blossoms
   1 1 2 3 5 8 13 21

   输出样例2

   8