#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
const int N = 152;
int dp[N][N][N];
int b[N][N];
int a[N];
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  string s;
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    if (a[i] == -1) {
      a[i] = -100000000;
    }
  }
  cin >> s;
  memset(dp, -63, sizeof dp);
  for (int i = 0; i < N - 1; i++) {
    dp[i][i + 1][1] = 0;
    dp[i][i][0] = 0;
  }
  for (int l = n; l > 0; l--) {
    for (int r = l + 1; r <= n + 1; r++) {
      for (int len = 2; len <= r - l; len++) {
        for (int m = l + 1; m < r; m++) {
          dp[l][r][len] = max(dp[l][r][len], dp[l][m][0] + dp[m][r][len]);
        }
        for (int m = r - 1; m > l - 1; m--) {
          dp[l][r][len] =
              max(dp[l][r][len], dp[m + 1][r][0] + dp[l][m + 1][len]);
        }
        if (s[l - 1] == s[r - 2]) {
          dp[l][r][len] = max(dp[l][r][len], dp[l + 1][r - 1][len - 2]);
        }
      }
      for (int m = l; m < r; m++) {
        dp[l][r][1] = max(dp[l][r][1], dp[l][m][0] + dp[m + 1][r][0]);
      }
      for (int m = 1; m < r - l + 1; m++) {
        dp[l][r][0] = max(dp[l][r][0], dp[l][r][m] + a[m]);
      }
    }
  }
  for (int l = n; l > 0; l--) {
    for (int r = l + 1; r <= n + 1; r++) {
      b[l][r] = max(b[l][r], dp[l][r][0]);
      for (int m = l; m < r; m++) {
        b[l][r] = max(b[l][r], b[l][m] + b[m + 1][r]);
      }
    }
  }
  cout << b[1][n + 1];
}
