#include <bits/stdc++.h>
using namespace std;
int n;
int a[155], ans[155];
int g[155][155];
int f[155][155][155];
char s[155];
template <class T>
void chkmax(T &a, T b) {
  if (a < b) a = b;
}
void calc() {
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= n; j++)
      for (int k = 0; k <= n; k++) f[i][j][k] = -1000000007;
  for (int i = 0; i < n; i++) g[i + 1][i] = 0;
  for (int i = n; i; i--)
    for (int j = i; j <= n; j++) {
      g[i][j] = -1000000007;
      for (int k = 1; i + k - 1 <= j; k++) {
        if (s[i] == s[j]) {
          if (k == 1)
            f[i][j][k] = max(g[i + 1][j], g[i][j - 1]);
          else if (k == 2)
            chkmax(f[i][j][k], g[i + 1][j - 1]);
          else
            chkmax(f[i][j][k], f[i + 1][j - 1][k - 2]);
        }
        for (int r = i; r < j; r++) {
          chkmax(f[i][j][k], f[i][r][k] + g[r + 1][j]);
          chkmax(f[i][j][k], g[i][r] + f[r + 1][j][k]);
        }
        chkmax(g[i][j], a[k] + f[i][j][k]);
      }
    }
  ans[0] = 0;
  for (int i = 1; i <= n; i++) {
    ans[i] = ans[i - 1];
    for (int j = 1; j <= i; j++) {
      chkmax(ans[i], ans[j - 1] + g[j][i]);
    }
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d ", &a[i]);
    if (a[i] == -1) a[i] = -1000000007;
  }
  gets(s + 1);
  calc();
  printf("%d\n", ans[n]);
}
