#include <bits/stdc++.h>
using namespace std;
int n, i, j, k;
int A[151], B[151][151], F[151][151], T[151][151][151];
char str[151];
int b(int i, int j);
int f(int i, int j);
int t(int i, int j, int k);
int b(int i, int j) {
  int &res = B[i][j], k;
  if (res == -1) {
    res = max(f(i, j), 0);
    for (k = i; k < j; k++) res = max(res, b(i, k) + b(k + 1, j));
  }
  return res;
}
int f(int i, int j) {
  int &res = F[i][j], k;
  if (res == -1)
    if (i > j)
      res = 0;
    else
      for (k = 1, res = -1000000000; k <= j - i + 1; k++)
        if (A[k] != -1) res = max(res, t(i, j, k) + A[k]);
  return res;
}
int t(int i, int j, int k) {
  int &res = T[i][j][k], p;
  if (res == -1) {
    if (k == 0)
      res = f(i, j);
    else if (k == 1)
      if (i == j)
        res = 0;
      else {
        res = max(f(i + 1, j), f(i, j - 1));
        for (p = i + 1; p < j; p++) res = max(res, f(i, p - 1) + f(p + 1, j));
      }
    else if (k > j - i + 1)
      res = -1000000000;
    else {
      if (str[i] == str[j])
        res = t(i + 1, j - 1, k - 2);
      else
        res = -1000000000;
      for (p = i + 1; p <= j; p++) res = max(res, f(i, p - 1) + t(p, j, k));
      for (p = i; p < j; p++) res = max(res, f(p + 1, j) + t(i, p, k));
    }
  }
  return res;
}
int main() {
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%d", &A[i]);
  scanf("%s", str);
  memset(B, -1, sizeof B);
  memset(F, -1, sizeof F);
  memset(T, -1, sizeof T);
  printf("%d\n", b(0, n - 1));
  return 0;
}
