#include <bits/stdc++.h>
using namespace ::std;
const int maxn = 151;
const int mod = 1e9 + 7;
const int inf = 1e8 + 500;
int dp[maxn][maxn];
int full[maxn][maxn];
int dpp[maxn][maxn][maxn];
int c[maxn];
int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> c[i];
  }
  string s;
  cin >> s;
  for (int i = 0; i < maxn; i++) {
    for (int j = 0; j < maxn; j++) {
      full[i][j] = -inf;
      for (int k = 0; k < maxn; k++) {
        dpp[i][j][k] = -inf;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    if (c[1] != -1) {
      full[i][i] = c[1];
    }
    dpp[i][i][1] = 0;
  }
  for (int t = 2; t <= n; t++) {
    for (int l = 0; l + t - 1 < n; l++) {
      int r = l + t - 1;
      for (int j = 1; j <= t; j++) {
        for (int i = l; i < r; i++) {
          dpp[l][r][j] = max(dpp[l][r][j], full[l][i] + dpp[i + 1][r][j]);
          dpp[l][r][j] = max(dpp[l][r][j], dpp[l][i][j] + full[i + 1][r]);
        }
        if (s[l] == s[r] && j != 1) {
          if (j > 2) {
            dpp[l][r][j] = max(dpp[l][r][j], dpp[l + 1][r - 1][j - 2]);
          } else {
            if (t == 2) {
              dpp[l][r][j] = 0;
            }
            dpp[l][r][j] = max(dpp[l][r][j], full[l + 1][r - 1]);
          }
        }
        if (c[j] != -1) {
          full[l][r] = max(full[l][r], dpp[l][r][j] + c[j]);
        }
      }
    }
  }
  for (int i = 0; i < n; i++) {
    dp[i][i] = max((int)0, c[1]);
  }
  for (int t = 2; t <= n; t++) {
    for (int l = 0; l + t - 1 < n; l++) {
      int r = l + t - 1;
      for (int i = l; i < r; i++) {
        dp[l][r] = max(dp[l][r], dp[l][i] + dp[i + 1][r]);
      }
      dp[l][r] = max(dp[l][r], full[l][r]);
    }
  }
  cout << dp[0][n - 1];
}
