#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
const int N = 155;
const long long mod = 1e9 + 7;
const long long inf = 1e10;
const int LOG = 20;
long long pw(long long a, long long b, long long M = mod, long long ret = 1) {
  while (b) {
    ret = ret * (b & 1 ? a : 1) % M, a = a * a % M, b >>= 1;
  }
  return ret;
}
char C[N];
string s;
int n, is[N][N];
long long A[N], Ans[N][N], dp[N][N][N];
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &A[i]);
    if (A[i] == -1) A[i] = -inf;
  }
  scanf("%s", C);
  s = C;
  s = "." + s;
  for (int i = 1; i <= n; i++) {
    Ans[i][i] = max(0ll, A[1]);
    dp[i][i][1] = 0;
    dp[i][i][0] = A[1];
    is[i][i] = 1;
    is[i + 1][i] = is[i][i - 1] = 1;
    for (int x = 2; x < N; x++) dp[i][i][x] = -inf;
  }
  for (int len = 2; len <= n; len++) {
    for (int l = 1; l <= n - len + 1; l++) {
      int r = l + len - 1;
      for (int x = 0; x < N; x++) dp[l][r][x] = -inf;
      is[l][r] = is[l + 1][r - 1] & (s[l] == s[r]);
      dp[l][r][len] = (is[l][r] ? 0 : -inf);
      for (int x = len - 1; x >= 0; x--) {
        for (int mid = l; mid < r; mid++) {
          dp[l][r][x] = max({dp[l][r][x], dp[l][mid][x] + dp[mid + 1][r][0],
                             dp[l][mid][0] + dp[mid + 1][r][x]});
        }
        if (x == 1) {
          dp[l][r][x] = max(dp[l][r][x], dp[l + 1][r][0]);
        }
        for (int mid = l + x - 1; mid <= r; mid++) {
          if (x >= 2 && s[l] == s[mid])
            dp[l][r][x] =
                max(dp[l][r][x], dp[l + 1][mid - 1][x - 2] + dp[mid + 1][r][0]);
        }
        for (int mid = l; mid <= r - x; mid++) {
          dp[l][r][x] = max(dp[l][r][x], dp[l][mid][0] + dp[mid + 1][r][x]);
        }
      }
      for (int x = 1; x <= len; x++) {
        dp[l][r][0] = max(dp[l][r][0], dp[l][r][x] + A[x]);
      }
    }
  }
  for (int len = 2; len <= n; len++) {
    for (int l = 1; l <= n - len + 1; l++) {
      int r = l + len - 1;
      Ans[l][r] = max(Ans[l][r], dp[l][r][0]);
      for (int mid = l; mid < r; mid++) {
        Ans[l][r] = max(Ans[l][r], Ans[l][mid] + Ans[mid + 1][r]);
      }
    }
  }
  printf("%lld\n", Ans[1][n]);
  return 0;
}
