#include <bits/stdc++.h>
using namespace std;
const int MX = 155;
const int INF = 100000000;
void relax(int& a, int b) { a = max(a, b); }
int c[MX];
int best[MX][MX];
int f[MX][MX][MX];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> c[i];
    if (c[i] == -1) c[i] = -INF;
  }
  string s;
  cin >> s;
  for (int l = 0; l < n; l++) {
    for (int r = 0; r < n; r++) {
      for (int len = 0; len <= n; len++) {
        f[l][r][len] = -INF;
      }
    }
  }
  for (int x = 1; x <= n; x++) {
    for (int l = 0, r = l + x - 1; r < n; l++, r++) {
      for (int len = 1; len <= x; len++) {
        for (int m = l; m <= r - 1; m++) {
          relax(f[l][r][len], f[l][m][0] + f[m + 1][r][len]);
          relax(f[l][r][len], f[l][m][len] + f[m + 1][r][0]);
        }
        if (s[l] == s[r]) {
          if (r - l > 1 && len >= 2) {
            relax(f[l][r][len], f[l + 1][r - 1][len - 2]);
          } else if (r - l + 1 == len) {
            relax(f[l][r][len], 0);
          }
        }
        relax(f[l][r][0], c[len] + f[l][r][len]);
      }
      best[l][r] = f[l][r][0];
      for (int m = l; m <= r; m++) {
        relax(best[l][r], (m - 1 >= 0 ? best[l][m - 1] : 0) + best[m + 1][r]);
      }
    }
  }
  cout << best[0][n - 1] << "\n";
}
