Problem: Market stalls now have the long-awaited game The Colder Scrools V: Nvodsk. The game turned out to be difficult as hell and most students can't complete the last quest ("We don't go to Nvodsk..."). That threatened winter exams. The rector already started to wonder whether he should postpone the winter exams till April (in fact, he wanted to complete the quest himself). But all of a sudden a stranger appeared at the door of his office. "Good afternoon. My name is Chuck and I solve any problems" — he said.

And here they are sitting side by side but still they can't complete the mission. The thing is, to kill the final boss one should prove one's perfect skills in the art of managing letters. One should be a real magician to do that. And can you imagine what happens when magicians start competing... 

But let's put it more formally: you are given a string and a set of integers ai. You are allowed to choose any substring that is a palindrome and delete it. At that we receive some number of points equal to ak, where k is the length of the deleted palindrome. For some k, ak = -1, which means that deleting palindrome strings of such length is forbidden. After a substring is deleted, the remaining part "shifts together", that is, at no moment of time the string has gaps. The process is repeated while the string has at least one palindrome substring that can be deleted. All gained points are summed up.

Determine what maximum number of points can be earned.

"Oh" — said Chuck, raising from the chair, — "I used to love deleting palindromes, just like you, but one day I took an arrow in the Knee".

Input

The first line contains an integer l (1 ≤ l ≤ 150) — the length of the string.

The second line contains exactly l integers ak ( - 1 ≤ ak ≤ 105) — the points a player gains for deleting.

The third line contains exactly l lowercase Latin letters — the original string from which a player can delete palindromes. The line contains no other characters apart from the newline character at the end of the string.

Output

Print a single number — the maximum number of points one can gain if he plays on the given string.

Examples

Input

7
-1 -1 -1 -1 -1 -1 -1
abacaba


Output

0


Input

7
1 -1 -1 -1 -1 -1 -1
abacaba


Output

7


Input

7
1 5 -1 -1 -1 -1 10
abacaba


Output

16

Note

In the first sample we cannot delete any substring, so the best result is 0. In the second sample we are allowed to delete only those palindromes whose length equals 1, thus, if we delete the whole string, we get 7 points. In the third sample the optimal strategy is: first we delete character c, then string aa, then bb, and the last one aa. At that we get 1 + 3 * 5 = 16 points.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const long long int MOD = 1000000007;
const long long BIG = 1446803456761533460LL;
const int Big = 336860180;
const long long int INF = LONG_LONG_MAX;
const vector<vector<long long int> > adj4({{0, 1}, {0, -1}, {1, 0}, {-1, 0}});
const vector<vector<long long int> > adj8(
    {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {-1, -1}, {1, -1}, {-1, 1}, {1, 1}});
long long int gcd(long long int a, long long int b) {
  return b == 0 ? a : gcd(b, a % b);
}
bool isprime(long long int n) {
  if (n == 2 || n == 3) return true;
  if (n < 2 || n % 2 == 0 || n % 3 == 0) return false;
  for (long long int i = 6; (i - 1) * (i - 1) <= n; i += 6) {
    if (n % (i - 1) == 0 || n % (i + 1) == 0) {
      return false;
    }
  }
  return true;
}
vector<bool> sprime;
void genPrime(long long int sz) {
  sprime = vector<bool>(sz, true);
  sprime[0] = false;
  sprime[1] = false;
  for (long long int i = (2); i < (sz); ++i) {
    if (sprime[i]) {
      for (long long int j = i * i; j < sz; j += i) {
        sprime[j] = false;
      }
    }
  }
}
long long int powMod(long long int a, long long int b, long long int mod) {
  long long int n = 1;
  long long int p = a;
  while (b > 0) {
    if (b % 2 == 1) {
      n *= p;
      n %= mod;
    }
    p *= p;
    p %= mod;
    b /= 2;
  }
  return n;
}
long long int modularInverse(long long int a, long long int mod) {
  return powMod(a, mod - 2, mod);
}
long long int binarysearch(long long int l, long long int r,
                           bool (*bsfunction)(long long int)) {
  while (r - l > 1) {
    long long int mid = (l + r) / 2;
    bool val = bsfunction(mid);
    if (val) {
      r = mid;
    } else {
      l = mid;
    }
  }
  return l;
}
stringstream sss;
const long long int maxn = 155;
long long int dp[2][maxn][maxn][maxn];
long long int memo[maxn][maxn][maxn];
long long int w[maxn];
string s;
void solve(long long int k, long long int i, long long int p) {
  if (memo[k][i][p]) return;
  memo[k][i][p] = 1;
  if (w[p * 2] != -1) {
    if (k == 0) {
      dp[0][k][i][p] = max(dp[0][k][i][p], (w[p * 2]));
      dp[1][k][i][p] = max(dp[1][k][i][p], (w[p * 2]));
    } else if (dp[1][k][i][0] != -1) {
      solve(k, i, 0);
      dp[0][k][i][p] = max(dp[0][k][i][p], (w[p * 2] + dp[1][k][i][0]));
      dp[1][k][i][p] = max(dp[1][k][i][p], (w[p * 2] + dp[1][k][i][0]));
    }
  }
  if (k == 0) return;
  solve(k - 1, i + 1, 0);
  solve(k - 1, i + 1, p);
  if (w[p * 2 + 1] != -1 && dp[1][k - 1][i + 1][0] != -1) {
    dp[0][k][i][p] =
        max(dp[0][k][i][p], (w[p * 2 + 1] + dp[1][k - 1][i + 1][0]));
    dp[1][k][i][p] =
        max(dp[1][k][i][p], (w[p * 2 + 1] + dp[1][k - 1][i + 1][0]));
  }
  dp[0][k][i][p] = max(dp[0][k][i][p], (dp[0][k - 1][i + 1][0]));
  if (w[1] != -1 && dp[1][k - 1][i + 1][p] != -1) {
    dp[0][k][i][p] = max(dp[0][k][i][p], (w[1] + dp[1][k - 1][i + 1][p]));
    dp[1][k][i][p] = max(dp[1][k][i][p], (w[1] + dp[1][k - 1][i + 1][p]));
  }
  for (long long int j = 1; j < k; ++j) {
    if (s[i] == s[i + j]) {
      solve(k - j - 1, i + j + 1, 0);
      solve(j - 1, i + 1, p + 1);
      solve(k - j - 1, i + j + 1, p);
      solve(j - 1, i + 1, 1);
      if (dp[1][k - j - 1][i + j + 1][0] != -1) {
        dp[0][k][i][p] = max(dp[0][k][i][p], (dp[0][j - 1][i + 1][p + 1] +
                                              dp[1][k - j - 1][i + j + 1][0]));
      }
      if (dp[1][j - 1][i + 1][1] != -1) {
        dp[0][k][i][p] = max(dp[0][k][i][p], (dp[1][j - 1][i + 1][1] +
                                              dp[0][k - j - 1][i + j + 1][p]));
      }
      if (dp[1][j - 1][i + 1][p + 1] != -1 &&
          dp[1][k - j - 1][i + j + 1][0] != -1) {
        dp[1][k][i][p] = max(dp[1][k][i][p], (dp[1][j - 1][i + 1][p + 1] +
                                              dp[1][k - j - 1][i + j + 1][0]));
      }
      if (dp[1][j - 1][i + 1][1] != -1 &&
          dp[1][k - j - 1][i + j + 1][p] != -1) {
        dp[1][k][i][p] = max(dp[1][k][i][p], (dp[1][j - 1][i + 1][1] +
                                              dp[1][k - j - 1][i + j + 1][p]));
      }
    }
  }
}
void MAIN() {
  memset(w, -1, sizeof w);
  long long int n;
  cin >> n;
  for (long long int i = 0; i < (n); ++i) {
    cin >> w[i + 1];
  }
  cin >> s;
  long long int mx = 0;
  memset(dp[1], -1, sizeof dp[1]);
  for (long long int i = 0; i <= n; ++i) {
    dp[1][0][i][0] = 0;
  }
  solve(n, 0, 0);
  cout << (dp[0][n][0][0]) << endl;
}
const long long int TESTCASEN = 1;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(10);
  sss << R"(
50
0 11 0 26 32 44 54 -1 83 -1 117 -1 -1 -1 231 -1 292 332 368 392 439 493 538 586 616 667 722 -1 851 906 -1 -1 -1 1165 1227 -1 1372 1434 -1 1603 1673 1759 1841 1936 2028 2121 2205 2304 2393 -1
cccbcbacbabbcabccabbabcbcabacbbabbcccacabbcacaccca
9
1 5 -1 -1 -1 -1 10 -1 -1
abacddaba
    )";
  for (long long int i = 0; i < (TESTCASEN); ++i) {
    MAIN();
  }
  return 0;
}