package main

import (
	"bufio"
	"fmt"
	"os"
)

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var l int
	if _, err := fmt.Fscan(reader, &l); err != nil {
		return
	}

	a := make([]int, l+1)
	for i := 1; i <= l; i++ {
		fmt.Fscan(reader, &a[i])
	}

	var s string
	fmt.Fscan(reader, &s)
	s = " " + s // 1-based indexing

	const INF = int(1e9)

	dp := make([][][]int, l+2)
	for i := range dp {
		dp[i] = make([][]int, l+2)
		for j := range dp[i] {
			dp[i][j] = make([]int, l+2)
			for k := range dp[i][j] {
				dp[i][j][k] = -INF
			}
		}
	}

	E := make([][]int, l+2)
	for i := range E {
		E[i] = make([]int, l+2)
		for j := range E[i] {
			E[i][j] = -INF
		}
	}

	for i := 1; i <= l+1; i++ {
		E[i][i-1] = 0 
	}

	for i := 1; i <= l; i++ {
		dp[i][i][1] = 0
		if a[1] != -1 {
			E[i][i] = a[1]
		}
	}

	for length := 2; length <= l; length++ {
		for i := 1; i <= l-length+1; i++ {
			j := i + length - 1

			for k := 1; k <= length; k++ {
				res := -INF
				
				// Option 1: Strip a completely deleted prefix
				for m := i; m < j; m++ {
					v1 := E[i][m]
					if v1 != -INF {
						v2 := dp[m+1][j][k]
						if v2 != -INF {
							if v1+v2 > res {
								res = v1 + v2
							}
						}
					}
				}

				// Option 2: Strip a completely deleted suffix
				for m := i + 1; m <= j; m++ {
					v1 := dp[i][m-1][k]
					if v1 != -INF {
						v2 := E[m][j]
						if v2 != -INF {
							if v1+v2 > res {
								res = v1 + v2
							}
						}
					}
				}

				// Option 3: Match the outward characters of the palindrome
				if s[i] == s[j] {
					if k == 2 {
						v := E[i+1][j-1]
						if v != -INF {
							if v > res {
								res = v
							}
						}
					} else if k > 2 {
						v := dp[i+1][j-1][k-2]
						if v != -INF {
							if v > res {
								res = v
							}
						}
					}
				}

				dp[i][j][k] = res
			}

			resE := -INF
			// Completely delete the current substring by reducing it to a single palindrome
			for k := 1; k <= length; k++ {
				if dp[i][j][k] != -INF && a[k] != -1 {
					if dp[i][j][k]+a[k] > resE {
						resE = dp[i][j][k] + a[k]
					}
				}
			}

			// Completely delete the current substring by splitting into two adjacent completely deleted blocks
			for m := i; m < j; m++ {
				v1 := E[i][m]
				if v1 != -INF {
					v2 := E[m+1][j]
					if v2 != -INF {
						if v1+v2 > resE {
							resE = v1 + v2
						}
					}
				}
			}

			E[i][j] = resE
		}
	}

	F := make([]int, l+1)
	F[0] = 0
	for i := 1; i <= l; i++ {
		F[i] = F[i-1] 
		for j := 1; j <= i; j++ {
			if E[j][i] != -INF {
				if F[j-1]+E[j][i] > F[i] {
					F[i] = F[j-1] + E[j][i]
				}
			}
		}
	}

	fmt.Println(F[l])
}