#include <bits/stdc++.h>
auto clk = clock();
const int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
const int dx8[] = {-1, -1, -1, 0, 1, 1, 1, 0},
          dy8[] = {-1, 0, 1, 1, 1, 0, -1, -1};
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long Gcd(long long a, long long b) {
  if (a % b == 0) return b;
  return Gcd(b, a % b);
}
long long Max(long long a, long long b) {
  if (a > b) return a;
  return b;
}
long long Min(long long a, long long b) {
  if (a < b) return a;
  return b;
}
void printvector(std::vector<long long> v) {
  for (int i = 0; i < v.size(); ++i) {
    cout << v[i] << " ";
  }
  cout << "" << endl;
}
void printarray(long long a[], long long n) {
  for (long long i = 0; i < n; ++i) {
    cout << a[i] << " ";
  }
  cout << "" << endl;
}
long long findlcm(vector<long long> arr, long long n) {
  long long ans = arr[0];
  for (int i = 1; i < n; i++) ans = (((arr[i] * ans)) / (Gcd(arr[i], ans)));
  return ans;
}
long long gcdExtended(long long a, long long b, long long *x, long long *y) {
  if (a == 0) {
    *x = 0, *y = 1;
    return b;
  }
  long long x1, y1;
  long long gcd = gcdExtended(b % a, a, &x1, &y1);
  *x = y1 - (b / a) * x1;
  *y = x1;
  return gcd;
}
long long power(long long x, long long y, long long p) {
  long long res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long modInverse(long long a, long long m) {
  long long x, y;
  long long g = gcdExtended(a, m, &x, &y);
  if (g != 1)
    return -1;
  else {
    long long res = (x % m + m) % m;
    return res;
  }
}
long long inverse(long long x, long long mod) { return power(x, mod - 2, mod); }
vector<long long> primeFactors(long long n) {
  vector<long long> v;
  while (n % 2 == 0) {
    v.push_back(2);
    n = n / 2;
  }
  for (int i = 3; i <= sqrt(n); i = i + 2) {
    while (n % i == 0) {
      v.push_back(i);
      n = n / i;
    }
  }
  if (n > 2) v.push_back(n);
  return v;
}
long long lowerbound(long long k, vector<long long> v) {
  long long l = 0;
  long long size = v.size();
  long long r = size - 1;
  long long mid;
  while (l <= r) {
    mid = (l + r) / 2;
    if (v[mid] < k)
      l = mid + 1;
    else {
      r = mid - 1;
    }
  }
  return l;
}
long long upperbound(long long k, vector<long long> v) {
  long long l = 0;
  long long size = v.size();
  long long r = size - 1;
  long long mid;
  while (l <= r) {
    mid = (l + r) / 2;
    if (v[mid] > k)
      r = mid - 1;
    else {
      l = mid + 1;
    }
  }
  return l;
}
long long C[2001][2000];
void binomialCoeff(long long n, long long k) {
  long long i, j;
  for (i = 0; i <= n; i++) {
    for (j = 0; j <= k; j++) {
      if (j == 0 || j == i)
        C[i][j] = 1;
      else
        C[i][j] = (C[i - 1][j - 1] % 1000000007 + C[i - 1][j] % 1000000007) %
                  1000000007;
    }
  }
}
string convertToNewString(const string &s) {
  string newString = "@";
  for (long long i = 0; i < s.size(); i++) {
    newString += "#" + s.substr(i, 1);
  }
  newString += "#$";
  return newString;
}
string longestPalindromeSubstring(const string &s) {
  string Q = convertToNewString(s);
  long long c = 0, r = 0;
  long long P[Q.size() + 4];
  memset(P, 0, sizeof(P));
  for (long long i = 1; i < Q.size() - 1; i++) {
    long long iMirror = c - (i - c);
    if (r > i) {
      P[i] = min(r - i, P[iMirror]);
    }
    while (Q[i + 1 + P[i]] == Q[i - 1 - P[i]]) {
      P[i]++;
    }
    if (i + P[i] > r) {
      c = i;
      r = i + P[i];
    }
  }
  int maxPalindrome = 0;
  int centerIndex = 0;
  for (int i = 1; i < Q.size() - 1; i++) {
    if (P[i] > maxPalindrome) {
      maxPalindrome = P[i];
      centerIndex = i;
    }
  }
  cout << maxPalindrome << "\n";
  return s.substr((centerIndex - 1 - maxPalindrome) / 2, maxPalindrome);
}
long long spf[100010];
void sieve() {
  spf[1] = 1;
  for (int i = 2; i < 100010; i++) spf[i] = i;
  for (int i = 4; i < 100010; i += 2) spf[i] = 2;
  for (int i = 3; i * i < 100010; i++) {
    if (spf[i] == i) {
      for (int j = i * i; j < 100010; j += i)
        if (spf[j] == j) spf[j] = i;
    }
  }
}
long long binarySearch(long long arr[], long long l, long long r, long long x) {
  if (r >= l) {
    long long mid = l + (r - l) / 2;
    if (arr[mid] == x) return mid;
    if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x);
    return binarySearch(arr, mid + 1, r, x);
  }
  return -1;
}
const long long N = 100000;
long long n;
long long tree[2 * N];
void build(long long arr[]) {
  for (long long i = 0; i < n; i++) {
    tree[n + i] = arr[i];
  }
  for (long long i = n - 1; i > 0; --i) {
    tree[i] = tree[i << 1] + tree[i << 1 | 1];
  }
}
void updateTreeNode(long long p, long long value) {
  tree[p + n] = value;
  p = p + n;
  for (long long i = p; i > 1; i >>= 1) {
    tree[i >> 1] = tree[i] + tree[i ^ 1];
  }
}
long long query(long long l, long long r) {
  long long res = 0;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l & 1) {
      res += tree[l++];
    }
    if (r & 1) {
      res += tree[--r];
    }
  }
  return res;
}
vector<long long> shortPath(vector<pair<long long, long long> > v[],
                            long long src, long long V = 0) {
  set<pair<long long, long long> > setds;
  long long sizee = V;
  long long IN = LLONG_MAX;
  vector<long long> dist(sizee, IN);
  vector<bool> vis(sizee, false);
  setds.insert(make_pair(0, src));
  dist[src] = 0;
  while (!setds.empty()) {
    pair<long long, long long> tmp = *(setds.begin());
    setds.erase(setds.begin());
    long long u = tmp.second;
    if (vis[u]) continue;
    vis[u] = true;
    vector<pair<long long, long long> >::iterator i;
    for (auto i = v[u].begin(); i != v[u].end(); ++i) {
      long long v = (*i).first;
      long long weight = (*i).second;
      if (dist[v] > dist[u] + weight) {
        if (dist[v] != LLONG_MAX)
          setds.erase(setds.find(make_pair(dist[v], v)));
        dist[v] = dist[u] + weight;
        setds.insert(make_pair(dist[v], v));
      }
    }
  }
  return dist;
}
long long root(long long a[], long long r) {
  if (a[r] == r) {
    return r;
  } else {
    long long x = root(a, a[r]);
    a[r] = x;
    return x;
  }
}
void unio(long long a[], long long size[], long long x, long long y) {
  x = root(a, x);
  y = root(a, y);
  if (x == y) {
    return;
  }
  if (size[x] >= size[y]) {
    a[y] = x;
    size[x] += size[y];
  } else {
    a[x] = y;
    size[y] += size[x];
  }
}
void dfs(std::vector<long long> v[], long long s, bool visited[]) {
  visited[s] = true;
  for (long long i = 0; i < v[s].size(); ++i) {
    if (!visited[v[s][i]]) {
      dfs(v, v[s][i], visited);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long txt = 1;
  while (txt--) {
    cin >> n;
    vector<long long> suf(n, 0);
    vector<long long> sufb(n, 0);
    vector<long long> pre(n, 0);
    vector<long long> p(n);
    string s;
    long long mx = 0;
    for (int i = 0, _n = (n); i < _n; i++) cin >> p[i];
    cin >> s;
    for (int i = 0, _n = (n); i < _n; i++) {
      if (!i) {
        if (s[i] == 'B') sufb[i] = p[i];
      } else {
        if (s[i] == 'B')
          sufb[i] = p[i] + sufb[i - 1];
        else {
          sufb[i] = sufb[i - 1];
        }
      }
    }
    for (int i = n - 1; i >= 0; i--) {
      if (i == n - 1) {
        if (s[i] == 'B') {
          pre[i] = p[i];
        }
        continue;
      }
      if (s[i] == 'B') {
        pre[i] = p[i] + pre[i + 1];
      } else {
        pre[i] = pre[i + 1];
      }
    }
    long long sum = 0;
    long long sumb = 0;
    long long suma = 0;
    for (int i = n - 1; i >= 0; i--) {
      sum += p[i];
      if (s[i] == 'A') {
        suma += p[i];
        if (i)
          mx = max(suma + sufb[i - 1], mx), mx = max(sumb + sufb[i - 1], mx);
        else {
          mx = max(sumb, mx);
          mx = max(suma, mx);
        }
      } else {
        sumb += p[i];
        if (i)
          mx = max(sumb + sufb[i - 1], mx);
        else {
          mx = max(sumb, mx);
        }
      }
    }
    suma = sumb = 0;
    for (int i = 0, _n = (n); i < _n; i++) {
      if (s[i] == 'A') {
        suma += p[i];
        if (i != n - 1)
          mx = max(sumb + pre[i + 1], mx), mx = max(suma + pre[i + 1], mx);
        else {
          mx = max(sumb, mx);
          mx = max(suma, mx);
        }
      } else {
        sumb += p[i];
        if (i != n - 1)
          mx = max(sumb + pre[i + 1], mx), mx = max(suma + pre[i + 1], mx);
        else {
          mx = max(sumb, mx);
          mx = max(suma, mx);
        }
      }
    }
    cout << mx << endl;
  }
}

### Prompt

Please create a solution in CPP to the following problem:

Alice and Bob are playing a game. The game involves splitting up game pieces into two teams. There are n pieces, and the i-th piece has a strength pi.

The way to split up game pieces is split into several steps:

  1. First, Alice will split the pieces into two different groups A and B. This can be seen as writing the assignment of teams of a piece in an n character string, where each character is A or B. 
  2. Bob will then choose an arbitrary prefix or suffix of the string, and flip each character in that suffix (i.e. change A to B and B to A). He can do this step at most once. 
  3. Alice will get all the pieces marked A and Bob will get all the pieces marked B. 



The strength of a player is then the sum of strengths of the pieces in the group.

Given Alice's initial split into two teams, help Bob determine an optimal strategy. Return the maximum strength he can achieve.

Input

The first line contains integer n (1 ≤ n ≤ 5·105) — the number of game pieces.

The second line contains n integers pi (1 ≤ pi ≤ 109) — the strength of the i-th piece.

The third line contains n characters A or B — the assignment of teams after the first step (after Alice's step).

Output

Print the only integer a — the maximum strength Bob can achieve.

Examples

Input

5
1 2 3 4 5
ABABA


Output

11


Input

5
1 2 3 4 5
AAAAA


Output

15


Input

1
1
B


Output

1

Note

In the first sample Bob should flip the suffix of length one.

In the second sample Bob should flip the prefix or the suffix (here it is the same) of length 5.

In the third sample Bob should do nothing.

### Response

```cpp
#include <bits/stdc++.h>
auto clk = clock();
const int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
const int dx8[] = {-1, -1, -1, 0, 1, 1, 1, 0},
          dy8[] = {-1, 0, 1, 1, 1, 0, -1, -1};
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long Gcd(long long a, long long b) {
  if (a % b == 0) return b;
  return Gcd(b, a % b);
}
long long Max(long long a, long long b) {
  if (a > b) return a;
  return b;
}
long long Min(long long a, long long b) {
  if (a < b) return a;
  return b;
}
void printvector(std::vector<long long> v) {
  for (int i = 0; i < v.size(); ++i) {
    cout << v[i] << " ";
  }
  cout << "" << endl;
}
void printarray(long long a[], long long n) {
  for (long long i = 0; i < n; ++i) {
    cout << a[i] << " ";
  }
  cout << "" << endl;
}
long long findlcm(vector<long long> arr, long long n) {
  long long ans = arr[0];
  for (int i = 1; i < n; i++) ans = (((arr[i] * ans)) / (Gcd(arr[i], ans)));
  return ans;
}
long long gcdExtended(long long a, long long b, long long *x, long long *y) {
  if (a == 0) {
    *x = 0, *y = 1;
    return b;
  }
  long long x1, y1;
  long long gcd = gcdExtended(b % a, a, &x1, &y1);
  *x = y1 - (b / a) * x1;
  *y = x1;
  return gcd;
}
long long power(long long x, long long y, long long p) {
  long long res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long modInverse(long long a, long long m) {
  long long x, y;
  long long g = gcdExtended(a, m, &x, &y);
  if (g != 1)
    return -1;
  else {
    long long res = (x % m + m) % m;
    return res;
  }
}
long long inverse(long long x, long long mod) { return power(x, mod - 2, mod); }
vector<long long> primeFactors(long long n) {
  vector<long long> v;
  while (n % 2 == 0) {
    v.push_back(2);
    n = n / 2;
  }
  for (int i = 3; i <= sqrt(n); i = i + 2) {
    while (n % i == 0) {
      v.push_back(i);
      n = n / i;
    }
  }
  if (n > 2) v.push_back(n);
  return v;
}
long long lowerbound(long long k, vector<long long> v) {
  long long l = 0;
  long long size = v.size();
  long long r = size - 1;
  long long mid;
  while (l <= r) {
    mid = (l + r) / 2;
    if (v[mid] < k)
      l = mid + 1;
    else {
      r = mid - 1;
    }
  }
  return l;
}
long long upperbound(long long k, vector<long long> v) {
  long long l = 0;
  long long size = v.size();
  long long r = size - 1;
  long long mid;
  while (l <= r) {
    mid = (l + r) / 2;
    if (v[mid] > k)
      r = mid - 1;
    else {
      l = mid + 1;
    }
  }
  return l;
}
long long C[2001][2000];
void binomialCoeff(long long n, long long k) {
  long long i, j;
  for (i = 0; i <= n; i++) {
    for (j = 0; j <= k; j++) {
      if (j == 0 || j == i)
        C[i][j] = 1;
      else
        C[i][j] = (C[i - 1][j - 1] % 1000000007 + C[i - 1][j] % 1000000007) %
                  1000000007;
    }
  }
}
string convertToNewString(const string &s) {
  string newString = "@";
  for (long long i = 0; i < s.size(); i++) {
    newString += "#" + s.substr(i, 1);
  }
  newString += "#$";
  return newString;
}
string longestPalindromeSubstring(const string &s) {
  string Q = convertToNewString(s);
  long long c = 0, r = 0;
  long long P[Q.size() + 4];
  memset(P, 0, sizeof(P));
  for (long long i = 1; i < Q.size() - 1; i++) {
    long long iMirror = c - (i - c);
    if (r > i) {
      P[i] = min(r - i, P[iMirror]);
    }
    while (Q[i + 1 + P[i]] == Q[i - 1 - P[i]]) {
      P[i]++;
    }
    if (i + P[i] > r) {
      c = i;
      r = i + P[i];
    }
  }
  int maxPalindrome = 0;
  int centerIndex = 0;
  for (int i = 1; i < Q.size() - 1; i++) {
    if (P[i] > maxPalindrome) {
      maxPalindrome = P[i];
      centerIndex = i;
    }
  }
  cout << maxPalindrome << "\n";
  return s.substr((centerIndex - 1 - maxPalindrome) / 2, maxPalindrome);
}
long long spf[100010];
void sieve() {
  spf[1] = 1;
  for (int i = 2; i < 100010; i++) spf[i] = i;
  for (int i = 4; i < 100010; i += 2) spf[i] = 2;
  for (int i = 3; i * i < 100010; i++) {
    if (spf[i] == i) {
      for (int j = i * i; j < 100010; j += i)
        if (spf[j] == j) spf[j] = i;
    }
  }
}
long long binarySearch(long long arr[], long long l, long long r, long long x) {
  if (r >= l) {
    long long mid = l + (r - l) / 2;
    if (arr[mid] == x) return mid;
    if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x);
    return binarySearch(arr, mid + 1, r, x);
  }
  return -1;
}
const long long N = 100000;
long long n;
long long tree[2 * N];
void build(long long arr[]) {
  for (long long i = 0; i < n; i++) {
    tree[n + i] = arr[i];
  }
  for (long long i = n - 1; i > 0; --i) {
    tree[i] = tree[i << 1] + tree[i << 1 | 1];
  }
}
void updateTreeNode(long long p, long long value) {
  tree[p + n] = value;
  p = p + n;
  for (long long i = p; i > 1; i >>= 1) {
    tree[i >> 1] = tree[i] + tree[i ^ 1];
  }
}
long long query(long long l, long long r) {
  long long res = 0;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l & 1) {
      res += tree[l++];
    }
    if (r & 1) {
      res += tree[--r];
    }
  }
  return res;
}
vector<long long> shortPath(vector<pair<long long, long long> > v[],
                            long long src, long long V = 0) {
  set<pair<long long, long long> > setds;
  long long sizee = V;
  long long IN = LLONG_MAX;
  vector<long long> dist(sizee, IN);
  vector<bool> vis(sizee, false);
  setds.insert(make_pair(0, src));
  dist[src] = 0;
  while (!setds.empty()) {
    pair<long long, long long> tmp = *(setds.begin());
    setds.erase(setds.begin());
    long long u = tmp.second;
    if (vis[u]) continue;
    vis[u] = true;
    vector<pair<long long, long long> >::iterator i;
    for (auto i = v[u].begin(); i != v[u].end(); ++i) {
      long long v = (*i).first;
      long long weight = (*i).second;
      if (dist[v] > dist[u] + weight) {
        if (dist[v] != LLONG_MAX)
          setds.erase(setds.find(make_pair(dist[v], v)));
        dist[v] = dist[u] + weight;
        setds.insert(make_pair(dist[v], v));
      }
    }
  }
  return dist;
}
long long root(long long a[], long long r) {
  if (a[r] == r) {
    return r;
  } else {
    long long x = root(a, a[r]);
    a[r] = x;
    return x;
  }
}
void unio(long long a[], long long size[], long long x, long long y) {
  x = root(a, x);
  y = root(a, y);
  if (x == y) {
    return;
  }
  if (size[x] >= size[y]) {
    a[y] = x;
    size[x] += size[y];
  } else {
    a[x] = y;
    size[y] += size[x];
  }
}
void dfs(std::vector<long long> v[], long long s, bool visited[]) {
  visited[s] = true;
  for (long long i = 0; i < v[s].size(); ++i) {
    if (!visited[v[s][i]]) {
      dfs(v, v[s][i], visited);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long txt = 1;
  while (txt--) {
    cin >> n;
    vector<long long> suf(n, 0);
    vector<long long> sufb(n, 0);
    vector<long long> pre(n, 0);
    vector<long long> p(n);
    string s;
    long long mx = 0;
    for (int i = 0, _n = (n); i < _n; i++) cin >> p[i];
    cin >> s;
    for (int i = 0, _n = (n); i < _n; i++) {
      if (!i) {
        if (s[i] == 'B') sufb[i] = p[i];
      } else {
        if (s[i] == 'B')
          sufb[i] = p[i] + sufb[i - 1];
        else {
          sufb[i] = sufb[i - 1];
        }
      }
    }
    for (int i = n - 1; i >= 0; i--) {
      if (i == n - 1) {
        if (s[i] == 'B') {
          pre[i] = p[i];
        }
        continue;
      }
      if (s[i] == 'B') {
        pre[i] = p[i] + pre[i + 1];
      } else {
        pre[i] = pre[i + 1];
      }
    }
    long long sum = 0;
    long long sumb = 0;
    long long suma = 0;
    for (int i = n - 1; i >= 0; i--) {
      sum += p[i];
      if (s[i] == 'A') {
        suma += p[i];
        if (i)
          mx = max(suma + sufb[i - 1], mx), mx = max(sumb + sufb[i - 1], mx);
        else {
          mx = max(sumb, mx);
          mx = max(suma, mx);
        }
      } else {
        sumb += p[i];
        if (i)
          mx = max(sumb + sufb[i - 1], mx);
        else {
          mx = max(sumb, mx);
        }
      }
    }
    suma = sumb = 0;
    for (int i = 0, _n = (n); i < _n; i++) {
      if (s[i] == 'A') {
        suma += p[i];
        if (i != n - 1)
          mx = max(sumb + pre[i + 1], mx), mx = max(suma + pre[i + 1], mx);
        else {
          mx = max(sumb, mx);
          mx = max(suma, mx);
        }
      } else {
        sumb += p[i];
        if (i != n - 1)
          mx = max(sumb + pre[i + 1], mx), mx = max(suma + pre[i + 1], mx);
        else {
          mx = max(sumb, mx);
          mx = max(suma, mx);
        }
      }
    }
    cout << mx << endl;
  }
}

```