CF1107E.Vasya and Binary String

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Vasya has a string ss of length nn consisting only of digits 0 and 1. Also he has an array aa of length nn .

Vasya performs the following operation until the string becomes empty: choose some consecutive substring of equal characters, erase it from the string and glue together the remaining parts (any of them can be empty). For example, if he erases substring 111 from string 111110 he will get the string 110. Vasya gets axa_x points for erasing substring of length xx .

Vasya wants to maximize his total points, so help him with this!

输入格式

The first line contains one integer nn ( 1n1001 \le n \le 100 ) — the length of string ss .

The second line contains string ss , consisting only of digits 0 and 1.

The third line contains nn integers a1,a2,ana_1, a_2, \dots a_n ( 1ai1091 \le a_i \le 10^9 ), where aia_i is the number of points for erasing the substring of length ii .

输出格式

Print one integer — the maximum total points Vasya can get.

输入输出样例

  • 输入#1

    7
    1101001
    3 4 9 100 1 2 3
    

    输出#1

    109
    
  • 输入#2

    5
    10101
    3 10 15 15 15
    

    输出#2

    23
    

说明/提示

In the first example the optimal sequence of erasings is: 1101001 \rightarrow 111001 \rightarrow 11101 \rightarrow 1111 \rightarrow \varnothing .

In the second example the optimal sequence of erasings is: 10101 \rightarrow 1001 \rightarrow 11 \rightarrow \varnothing .

首页