#include <bits/stdc++.h>
using namespace std;
char s[155];
const int INF = 1e9;
int a[155], best[155][155], f[155][155][155], flag, l, r, L, i, j, k, p, m, n;
void upd(int x) {
  if (x > f[i][j][k]) f[i][j][k] = x;
}
int main() {
  scanf("%d", &n);
  for (i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    if (a[i] == -1) a[i] = -INF;
  }
  scanf("%s", s + 1);
  for (i = 1; i <= n; i++)
    for (j = i; j <= n; j++)
      for (k = 0; k <= n; k++) f[i][j][k] = -INF;
  for (L = 1; L <= n; L++)
    for (i = 1; i <= n - L + 1; i++) {
      j = i + L - 1;
      if (L == 1) f[i][j][0] = a[1];
      for (m = i; m < j; m++)
        f[i][j][0] = max(f[i][j][0], f[i][m][0] + f[m + 1][j][0]);
      for (flag = 1, l = i, r = j; l < r; l++, r--)
        if (s[l] != s[r]) flag = 0;
      if (flag) f[i][j][0] = max(f[i][j][0], a[L]);
      for (m = i; m <= j; m++)
        f[i][j][1] = max(f[i][j][1], f[i][m - 1][0] + f[m + 1][j][0]);
      for (k = 2; k <= L; k++) {
        for (p = i + 1; p <= j; p++) upd(f[i][p - 1][0] + f[p][j][k]);
        for (p = i; p < j; p++) upd(f[p + 1][j][0] + f[i][p][k]);
        if (s[i] == s[j]) upd(f[i + 1][j - 1][k - 2]);
      }
      for (k = 1; k <= L; k++) f[i][j][0] = max(f[i][j][0], f[i][j][k] + a[k]);
      best[i][j] = max(0, f[i][j][0]);
      for (m = i; m < j; m++)
        best[i][j] = max(best[i][j], best[i][m] + best[m + 1][j]);
    }
  printf("%d\n", best[1][n]);
}
