#include <bits/stdc++.h>
using namespace std;
const int N = 155;
const int inf = 1000000000;
int dp[N][N][2 * N];
int dp2[N];
int cost[2 * N];
char s[N];
int main() {
  int n;
  while (scanf("%d", &n) == 1) {
    for (int i = 0; i < 2 * N; i++) cost[i] = -inf;
    for (int i = 1; i <= n; i++) {
      scanf("%d", &cost[i]);
      if (cost[i] == -1) cost[i] = -inf;
    }
    for (int i = 0; i < N; i++) {
      dp2[i] = -inf;
      for (int j = 0; j < N; j++)
        for (int k = 0; k < 2 * N; k++) {
          dp[i][j][k] = -inf;
          if (i > j && k == 0) dp[i][j][k] = 0;
        }
    }
    scanf("%s", s + 1);
    for (int len = 1; len <= n; len++) {
      for (int i = 1; i <= n; i++) {
        int j = i + len - 1;
        if (j > n) break;
        for (int mch = 0; mch <= n; mch++) {
          if (s[i] == s[j]) {
            int add = 1;
            if (i < j) add = 2;
            dp[i][j][mch] =
                max(dp[i][j][mch], dp[i + 1][j - 1][0] + cost[mch * 2 + add]);
            dp[i][j][mch] = max(dp[i][j][mch], dp[i + 1][j - 1][mch + 1]);
          }
          for (int k = i; k < j; k++) {
            dp[i][j][mch] = max(dp[i][j][mch], dp[i][k][mch] + dp[k + 1][j][0]);
            dp[i][j][mch] = max(dp[i][j][mch], dp[i][k][0] + dp[k + 1][j][mch]);
          }
        }
      }
    }
    dp2[0] = 0;
    for (int i = 1; i <= n; i++) {
      dp2[i] = dp2[i - 1];
      for (int j = 1; j <= i; j++) {
        dp2[i] = max(dp2[i], dp2[j - 1] + dp[j][i][0]);
      }
    }
    printf("%d\n", dp2[n]);
  }
  return 0;
}
