不可能的任务

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

给定一个字符串以及分数数组 $a_k$。你可以反复执行以下操作：选择当前字符串中的一个回文子串并删除，剩余字符自动拼接。

若删除的回文串长度为 $k$，你获得 $a_k$ 分；若 $a_k=-1$，则禁止删除长度为 $k$ 的回文串。你也可以随时停止。

求能够获得的最大总分。

输入格式

第一行包含字符串长度 $l$。

第二行包含 $l$ 个整数 $a_1,a_2,\ldots,a_l$。

第三行包含一个长度恰为 $l$ 的小写字母字符串。

输出格式

输出最大总得分。

样例输入 1

7
-1 -1 -1 -1 -1 -1 -1
abacaba

样例输出 1

0

样例输入 2

7
1 -1 -1 -1 -1 -1 -1
abacaba

样例输出 2

7

样例输入 3

7
1 5 -1 -1 -1 -1 10
abacaba

样例输出 3

16

数据范围

$1\le l\le150$，$-1\le a_k\le10^5$，字符串只含小写字母。

每个测试点独立计分。