#include <bits/stdc++.h>
using namespace std;
int n;
int c[155], dp[155][155], rem[155][155][155], ful[155][155];
bool vis[155][155], pal[155][155];
char s[155];
void solve(int bas, int son) {
  if (vis[bas][son]) return;
  vis[bas][son] = true;
  if (bas > son) return;
  if (bas == son) {
    ful[bas][son] = c[1];
    dp[bas][son] = max(dp[bas][son], c[1]);
    rem[bas][son][0] = c[1];
    rem[bas][son][1] = 0;
    return;
  }
  for (int i = bas; i < son; i++) {
    solve(bas, i);
    solve(i + 1, son);
  }
  if (pal[bas][son]) rem[bas][son][son - bas + 1] = 0;
  for (int i = 1; i <= son - bas; i++) {
    for (int j = 1; j <= son - bas; j++) {
      rem[bas][son][i] =
          max(rem[bas][son][i], ful[bas][bas + j - 1] + rem[bas + j][son][i]);
      rem[bas][son][i] =
          max(rem[bas][son][i], ful[son - j + 1][son] + rem[bas][son - j][i]);
    }
    if (i == 1) continue;
    if (s[bas] == s[son])
      rem[bas][son][i] = max(rem[bas][son][i], rem[bas + 1][son - 1][i - 2]);
  }
  for (int i = 1; i <= son - bas + 1; i++) {
    ful[bas][son] = max(ful[bas][son], rem[bas][son][i] + c[i]);
  }
  rem[bas][son][0] = ful[bas][son];
  dp[bas][son] = max(dp[bas][son], ful[bas][son]);
  for (int i = bas; i < son; i++) {
    dp[bas][son] = max(dp[bas][son], dp[bas][i] + dp[i + 1][son]);
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &c[i]);
    if (c[i] == -1) c[i] = -1000000000;
  }
  scanf("%s", s + 1);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n - i + 1; j++) {
      if (s[j] == s[j + i - 1]) {
        if (j + 1 >= j + i - 2) {
          pal[j][i + j - 1] = 1;
        } else {
          pal[j][i + j - 1] |= pal[j + 1][i + j - 2];
        }
      }
    }
  }
  for (int i = 0; i < 155; i++) {
    for (int j = 0; j < 155; j++) {
      for (int k = 0; k < 155; k++) {
        rem[i][j][k] = -1000000000;
      }
      ful[i][j] = -1000000000;
    }
  }
  solve(1, n);
  printf("%d", dp[1][n]);
}
