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 p_{i}.

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

  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.  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.  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·10^5) — the number of game pieces.

The second line contains n integers p_{i} (1 ≤ p_{i} ≤ 10^9) — 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.

Source: codeforces | Difficulty: MEDIUM
Tags: Complete search

Constructive algorithms


Solutions:
n = int(input())
a = list(map(int, input().split()))
s = input()
maxSuff = 0
cnt = 0
for i in range(n):
	if s[i] == 'A':
		maxSuff += a[i]
	else:
		cnt += a[i]
suff = []
suff.append(maxSuff)
for i in range(1, n):
	if s[i - 1] == 'A':
		suff.append(suff[i - 1] - a[i - 1])
	else:
		suff.append(suff[i - 1] + a[i - 1])
maxPref = 0
s = s[::-1]
a = a[::-1]
for i in range(n):
	if s[i] == 'A':
		maxPref += a[i]
pref = []
pref.append(maxPref)
for i in range(1, n):
	if s[i - 1] == 'A':
		pref.append(pref[i - 1] - a[i - 1])
	else:
		pref.append(pref[i - 1] + a[i - 1])
print(max(max(max(pref), max(suff)), cnt))


n = int(input())
strength = [int(i) for i in input().split()]
s = input()
total = 0
for i in range(n):
	if s[i] == 'B':
		total += strength[i]
prefix = [0] * n
suffix = [0] * n
for i in range(n):
	if s[i] == 'A':
		if i == 0:
			prefix[i] = 0 + strength[i]
		else:
			prefix[i] = prefix[i - 1] + strength[i]
	elif i == 0:
		prefix[i] = 0 - strength[i]
	else:
		prefix[i] = prefix[i - 1] - strength[i]
for i in range(n - 1, -1, -1):
	if s[i] == 'A':
		if i == n - 1:
			suffix[i] = 0 + strength[i]
		else:
			suffix[i] = suffix[i + 1] + strength[i]
	elif i == n - 1:
		suffix[i] = 0 - strength[i]
	else:
		suffix[i] = suffix[i + 1] - strength[i]
x = 0
for i in range(n):
	if prefix[i] > x:
		x = prefix[i]
for i in range(n):
	if suffix[i] > x:
		x = suffix[i]
total += x
print(str(total))


import sys
input = sys.stdin.readline
n = int(input())
powers = list(map(int, input().strip().split()))
teams = list(input().strip())
lefts = [0]
rights = [0]
without = 0
for i in range(n):
	if teams[i] == 'A':
		lefts.append(lefts[-1] + powers[i])
	else:
		lefts.append(lefts[-1] - powers[i])
		without += powers[i]
	if teams[n - i - 1] == 'A':
		rights.append(rights[-1] + powers[n - i - 1])
	else:
		rights.append(rights[-1] - powers[n - i - 1])
print(without + max(max(lefts), max(rights)))


n = int(input())
p = list(map(int, input().split()))
s = input()
maxi = 0
temp = 0
local = -1
for i in range(n):
	if s[i] == 'A':
		temp += p[i]
	else:
		temp -= p[i]
	if temp > maxi:
		local = i
		maxi = temp
ans = 0
for i in range(local + 1):
	if s[i] == 'A':
		ans += p[i]
for i in range(local + 1, n):
	if s[i] == 'B':
		ans += p[i]
maxi = 0
temp = 0
local = -1
p = list(reversed(p))
s = s[::-1]
for i in range(n):
	if s[i] == 'A':
		temp += p[i]
	else:
		temp -= p[i]
	if temp > maxi:
		local = i
		maxi = temp
ans1 = 0
for i in range(local + 1):
	if s[i] == 'A':
		ans1 += p[i]
for i in range(local + 1, n):
	if s[i] == 'B':
		ans1 += p[i]
print(max(ans, ans1))


def main():
	n = int(input())
	ps = [int(x) for x in input().split()]
	s = input()
	print(solver(ps, s))

def solver(ps, s):
	bestDScore = 0
	dScore = 0
	for i in range(len(s)):
		if s[i] == 'A':
			dScore += ps[i]
			if dScore > bestDScore:
				bestDScore = dScore
		elif s[i] == 'B':
			dScore -= ps[i]
		else:
			assert False
	dScore = 0
	for i in range(len(s) - 1, -1, -1):
		if s[i] == 'A':
			dScore += ps[i]
			if dScore > bestDScore:
				bestDScore = dScore
		elif s[i] == 'B':
			dScore -= ps[i]
		else:
			assert False
	bestScore = calculateScore(ps, s) + bestDScore
	return bestScore

def calculateScore(ps, s):
	score = 0
	for i in range(len(s)):
		if s[i] == 'B':
			score += ps[i]
	return score
main()


(n, t) = (int(input()), list(map(int, input().split())))
b = [q * (d == 'B') for (q, d) in zip(t, input())]
y = v = sum(b)
x = u = sum(t) - v
for i in range(n):
	u += 2 * b[i] - t[i]
	x = max(x, u)
	v += t[i] - 2 * b[i]
	y = max(y, v)
print(max(x, y))


n = int(input())
a = list(map(int, input().strip().split()))
s = str(input())
q = 0
m = 0
su = 0
for i in range(n):
	if s[i] == 'A':
		q += a[i]
		m = max(m, q)
	else:
		su += a[i]
		q -= a[i]
q = 0
for i in range(n - 1, -1, -1):
	if s[i] == 'A':
		q += a[i]
		m = max(m, q)
	else:
		q -= a[i]
print(su + m)


from sys import stdin
import operator
N = int(stdin.readline())
p = list(map(int, stdin.readline().strip().split(' ')))
teams = list(map(lambda x: 1 if x == 'B' else -1, stdin.readline().strip()))
values = list(map(operator.mul, p, teams))
start = sum(filter(lambda x: max(x, 0), values))
total = start
best = start
for i in values:
	total -= i
	best = max(total, best)
total = start
for i in reversed(values):
	total -= i
	best = max(total, best)
print(best)


import sys
n = int(sys.stdin.buffer.readline().decode('utf-8'))
a = list(map(int, sys.stdin.buffer.readline().decode('utf-8').split()))
s = sys.stdin.buffer.readline().decode('utf-8').rstrip()
bob = 0
for (i, c) in enumerate(s):
	if c == 'B':
		bob += a[i]
ans = bob
acc = 0
for (i, c) in enumerate(s):
	acc += a[i] * (1 if c == 'A' else -1)
	ans = max(ans, bob + acc)
acc = 0
for (i, c) in zip(range(n - 1, -1, -1), reversed(s)):
	acc += a[i] * (1 if c == 'A' else -1)
	ans = max(ans, bob + acc)
print(ans)


class CodeforcesTask632BSolution:

	def __init__(self):
		self.result = ''
		self.n = 0
		self.strengths = []
		self.teams = ''

	def read_input(self):
		self.n = int(input())
		self.strengths = [int(x) for x in input().split(' ')]
		self.teams = input()

	def process_task(self):
		a_score = 0
		b_score = 0
		for x in range(self.n):
			if self.teams[x] == 'A':
				a_score += self.strengths[x]
			else:
				b_score += self.strengths[x]
		mx_chng = 0
		res = 0
		resback = 0
		for for_mv in range(self.n):
			if self.teams[for_mv] == 'A':
				res += self.strengths[for_mv]
			else:
				res -= self.strengths[for_mv]
			mx_chng = max(mx_chng, res)
		for back_mv in range(self.n - 1, 0, -1):
			if self.teams[back_mv] == 'A':
				resback += self.strengths[back_mv]
			else:
				resback -= self.strengths[back_mv]
			mx_chng = max(mx_chng, resback)
		self.result = str(mx_chng + b_score)

	def get_result(self):
		return self.result
Solution = CodeforcesTask632BSolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


n = input()
s = [int(x) for x in input().split(' ')]
g = input()
A = 0
B = 0
for i in range(len(g)):
	if g[i] == 'A':
		A += s[i]
	else:
		B += s[i]
(startA, startB) = (A, B)
maximum = B
for i in range(len(g)):
	if g[i] == 'A':
		A -= s[i]
		B += s[i]
	else:
		A += s[i]
		B -= s[i]
	if B > maximum:
		maximum = B
(A, B) = (startA, startB)
for i in reversed(range(len(g))):
	if g[i] == 'A':
		A -= s[i]
		B += s[i]
	else:
		A += s[i]
		B -= s[i]
	if B > maximum:
		maximum = B
print(maximum)


n = int(input())
p = [int(_) for _ in input().split()]
s = input()
ans = 0
for i in range(n):
	if s[i] == 'B':
		ans += p[i]
tmp = 0
mx = 0
for i in range(n):
	tmp += p[i] if s[i] == 'A' else -p[i]
	mx = max(tmp, mx)
tmp = 0
for i in range(n)[::-1]:
	tmp += p[i] if s[i] == 'A' else -p[i]
	mx = max(tmp, mx)
ans += mx
print(ans)


n = int(input())
ps = [int(_) for _ in input().split()]
ps = [0] + ps + [0]
nps = ps[:]
s = input()
tot = sum([ps[i] for i in range(1, n + 1) if s[i - 1] == 'B'])
for i in range(1, n + 1):
	mult = 1 if s[i - 1] == 'A' else -1
	ps[i] = ps[i - 1] + mult * ps[i]
for i in range(n, 0, -1):
	mult = 1 if s[i - 1] == 'A' else -1
	nps[i] = nps[i + 1] + mult * nps[i]
mp = max(ps)
mn = max(nps)
print(max(mp, mn) + tot)


n = input()
strength = input()
chars = input()
strength = strength.split(' ')
cost = 0
for k in range(0, int(n)):
	if chars[k] == 'B':
		cost += int(strength[k])
temp = cost
temp_cost = temp
for j in range(0, int(n)):
	if chars[j] == 'A':
		temp_cost += int(strength[j])
	else:
		temp_cost -= int(strength[j])
	cost = max(cost, temp_cost)
temp_cost = temp
for j in range(int(n) - 1, 0, -1):
	if chars[j] == 'A':
		temp_cost += int(strength[j])
	else:
		temp_cost -= int(strength[j])
	cost = max(cost, temp_cost)
print(cost)


import sys
import math

def main():
	n = int(input())
	p = list(map(int, input().split()))
	s = input()
	prefa = [0] * n
	prefb = [0] * n
	for i in range(n):
		if i != 0:
			prefa[i] = prefa[i - 1]
			prefb[i] = prefb[i - 1]
		if s[i] == 'A':
			prefa[i] += p[i]
		else:
			prefb[i] += p[i]
	suffa = [0] * n
	suffb = [0] * n
	for i in reversed(range(n)):
		if i != n - 1:
			suffa[i] = suffa[i + 1]
			suffb[i] = suffb[i + 1]
		if s[i] == 'A':
			suffa[i] += p[i]
		else:
			suffb[i] += p[i]
	maxa = suffb[0]
	for i in range(n):
		t1 = prefa[i]
		if i != n - 1:
			t1 += suffb[i + 1]
		t2 = suffa[i]
		if i != 0:
			t2 += prefb[i - 1]
		maxa = max([maxa, t1, t2])
	print(maxa)
main()


import sys
import bisect
from bisect import bisect_left as lb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)

def hnbhai():
	n = sb()
	a = sd()
	s = list(sa())
	prefix1 = [0] * (n + 2)
	prefix2 = [0] * (n + 2)
	suffix1 = [0] * (n + 2)
	suffix2 = [0] * (n + 2)
	for i in range(1, n + 1):
		if s[i - 1] == 'A':
			prefix1[i] = prefix1[i - 1] + a[i - 1]
			prefix2[i] = prefix2[i - 1]
		else:
			prefix2[i] = prefix2[i - 1] + a[i - 1]
			prefix1[i] = prefix1[i - 1]
	for i in range(n, 0, -1):
		if s[i - 1] == 'A':
			suffix1[i] = suffix1[i + 1] + a[i - 1]
			suffix2[i] = suffix2[i + 1]
		else:
			suffix1[i] = suffix1[i + 1]
			suffix2[i] = suffix2[i + 1] + a[i - 1]
	max_ = 0
	for i in range(0, n + 1):
		max_ = max(max_, prefix1[i] + suffix2[i + 1])
		max_ = max(max_, suffix1[i] + prefix2[i - 1])
	print(max_)
for _ in range(1):
	hnbhai()


import sys
import itertools
f = sys.stdin
g = itertools.accumulate
n = int(f.readline())
p = list(map(int, f.readline().split()))
c = f.readline()
v = [-x if y == 'B' else x for (x, y) in zip(p, c)]
s = sum((p[i] if c[i] == 'B' else 0 for i in range(n)))
print(s + max(0, max(g(v)), max(g(v[::-1]))))


N = int(input())
arr = list(map(int, input().split()))
teams = input()
initial = sum((arr[i] for i in range(N) if teams[i] == 'B'))
best = initial
cur = initial
for i in range(N):
	if teams[i] == 'B':
		cur -= arr[i]
	else:
		cur += arr[i]
		if cur > best:
			best = cur
cur = initial
for i in range(N - 1, -1, -1):
	if teams[i] == 'B':
		cur -= arr[i]
	else:
		cur += arr[i]
		if cur > best:
			best = cur
print(best)


n = int(input())
a = list(map(int, input().split()))
s = input()
s = list(s)
sum_a = [0]
sum_b = [0]
for i in range(n):
	if i != 0:
		sum_a.append(sum_a[-1])
		sum_b.append(sum_b[-1])
	if s[i] == 'A':
		sum_a[-1] += a[i]
	else:
		sum_b[-1] += a[i]
aa = sum_b[-1] - sum_a[0]
ans = []
for i in range(n):
	ans.append(sum_b[-1] - sum_b[i] + sum_a[i])
s.reverse()
a.reverse()
sum_a = [0]
sum_b = [0]
for i in range(n):
	if i != 0:
		sum_a.append(sum_a[-1])
		sum_b.append(sum_b[-1])
	if s[i] == 'A':
		sum_a[-1] += a[i]
	else:
		sum_b[-1] += a[i]
for i in range(n):
	ans.append(sum_b[-1] - sum_b[i] + sum_a[i])
print(max(max(ans), aa))


def main():
	input()
	l = [(p, c == 'B') for (p, c) in zip(map(int, input().split()), input())]
	s = t = sum((p for (p, m) in l if m))
	res = [s]
	for (p, m) in l:
		if m:
			s -= p
		else:
			s += p
			res.append(s)
	for (p, m) in reversed(l):
		if m:
			t -= p
		else:
			t += p
			res.append(t)
	print(max(res))
main()


def main():
	input()
	pp = list(map(int, input().split()))
	mask = [c == 'B' for c in input()]
	s = t = sum((p for (p, m) in zip(pp, mask) if m))
	res = [s]
	for (p, m) in zip(pp, mask):
		if m:
			s -= p
		else:
			s += p
			res.append(s)
	pp.reverse()
	mask.reverse()
	for (p, m) in zip(pp, mask):
		if m:
			t -= p
		else:
			t += p
			res.append(t)
	print(max(res))

def __starting_point():
	main()
__starting_point()


n = int(input())
a = list(map(int, input().split()))
s = input()

def m(s, a):
	(q, w) = (0, 0)
	for i in range(n):
		if s[i] == 'A':
			q += a[i]
		else:
			w += a[i]
	r = w
	for i in range(n):
		if s[i] == 'A':
			w += a[i]
			q -= a[i]
		else:
			q += a[i]
			w -= a[i]
		r = max(r, w)
	return r
print(max(m(s, a), m(s[::-1], a[::-1])))


n = int(input())
power = list(map(int, input().split()))
s = input()
cnt = 0
for i in range(n):
	if s[i] == 'B':
		cnt += power[i]
ans = cnt
k = cnt
for i in range(n):
	if s[i] == 'B':
		k -= power[i]
	else:
		k += power[i]
	ans = max(ans, k)
k = cnt
for i in range(n - 1, -1, -1):
	if s[i] == 'B':
		k -= power[i]
	else:
		k += power[i]
	ans = max(ans, k)
print(ans)


n = int(input())
arr = list(map(int, input().split()))
s = input()
if n == 1:
	print(arr[0])
	exit()
pref_A = []
pref_B = []
summ = 0
for i in range(n):
	if s[i] == 'A':
		summ += arr[i]
		pref_A.append(summ)
	else:
		pref_A.append(summ)
summ = 0
for i in range(n):
	if s[i] == 'B':
		summ += arr[i]
		pref_B.append(summ)
	else:
		pref_B.append(summ)
suff_B = []
suff_A = []
summ = 0
for i in range(n - 1, -1, -1):
	if s[i] == 'A':
		summ += arr[i]
		suff_A.append(summ)
	else:
		suff_A.append(summ)
summ = 0
for i in range(n - 1, -1, -1):
	if s[i] == 'B':
		summ += arr[i]
		suff_B.append(summ)
	else:
		suff_B.append(summ)
suff_A = suff_A[::-1]
suff_B = suff_B[::-1]
ans = 0
for i in range(n):
	if i + 1 == n:
		ans = max(ans, pref_A[i])
	else:
		ans = max(ans, suff_B[i + 1] + pref_A[i])
for i in range(n - 1, -1, -1):
	if i - 1 == -1:
		ans = max(ans, suff_A[i])
	else:
		ans = max(ans, suff_A[i] + pref_B[i - 1])
ans = max(ans, max(pref_B), max(suff_B))
print(ans)


n = int(input())
p = input().split()
a = input()
sumA = 0
sumB = 0
for i in range(n):
	p[i] = int(p[i])
	if a[i] == 'B':
		sumB += p[i]
result = [sumB]
sumBLast = sumB
for i in range(n):
	if a[i] == 'A':
		sumB += p[i]
	if a[i] == 'B':
		sumB -= p[i]
	if a[n - i - 1] == 'A':
		sumBLast += p[n - i - 1]
	if a[n - i - 1] == 'B':
		sumBLast -= p[n - i - 1]
	result.append(sumB)
	result.append(sumBLast)
print(max(result))


n = int(input())
pi = list(map(int, input().split()))
ab = input()
numi = [0] * n
numi2 = [0] * n
if ab[0] == 'B':
	numi[0] = pi[0]
else:
	numi2[0] = pi[0]
for i in range(1, n):
	if ab[i] == 'B':
		numi[i] = numi[i - 1] + pi[i]
		numi2[i] = numi2[i - 1]
	else:
		numi2[i] = numi2[i - 1] + pi[i]
		numi[i] = numi[i - 1]
n2 = n - 1
maxi = numi[n2]
for i in range(n):
	maxi = max(maxi, numi[n2] - numi[i] + numi2[i])
for i in range(n - 2, -1, -1):
	maxi = max(maxi, numi[i] + numi2[n2] - numi2[i])
print(maxi)


n = int(input())
powers = [int(n) for n in input().split()]
marks = input()
Bob_power = sum([powers[i] for i in range(n) if marks[i] == 'B'])
max_Bob_power = Bob_power
start_Bob_power = Bob_power
for i in range(n):
	Bob_power += powers[i] * (1 if marks[i] == 'A' else -1)
	if max_Bob_power < Bob_power:
		max_Bob_power = Bob_power
Bob_power = start_Bob_power
for i in range(1, n + 1):
	Bob_power += powers[-i] * (1 if marks[-i] == 'A' else -1)
	if max_Bob_power < Bob_power:
		max_Bob_power = Bob_power
print(max_Bob_power)


import collections
import math
n = int(input())
p = list(map(int, input().split()))
s = input()

def solve(p, s):
	(a, b) = ([0] * n, [0] * n)
	m = 0
	if s[0] == 'B':
		b[0] = p[0]
		m += p[0]
	else:
		a[0] = p[0]
	for i in range(1, n):
		if s[i] == 'B':
			b[i] += p[i]
			m += p[i]
		else:
			a[i] += p[i]
		a[i] += a[i - 1]
		b[i] += b[i - 1]
	ans = m
	for i in range(n):
		if m - b[i] + a[i] > ans:
			ans = m - b[i] + a[i]
	return ans
print(max(solve(p, s), solve(p[::-1], s[::-1])))


power = 0
n = int(input())
powers = [int(x) for x in input().split(' ')]
alisa_move = input()

def power_at(i, powers):
	p = powers[i]
	return p
move = list(alisa_move)
move1 = []
move1.extend(reversed(list(alisa_move)))
p_max = 0
for i in range(0, n):
	if move[i] == 'B':
		p_max += power_at(i, powers)
p_temp = p_max
for i in range(0, n):
	if move[i] == 'A':
		move[i] = 'B'
		p_temp += power_at(i, powers)
		if p_max < p_temp:
			p_max = p_temp
	elif move[i] == 'B':
		move[i] = 'A'
		p_temp -= power_at(i, powers)
powers1 = []
powers1.extend(reversed(powers))
p_temp = 0
for i in range(0, n):
	if move1[i] == 'B':
		p_temp += power_at(i, powers1)
for i in range(0, n):
	if move1[i] == 'A':
		move1[i] = 'B'
		p_temp += power_at(i, powers1)
		if p_max < p_temp:
			p_max = p_temp
	elif move1[i] == 'B':
		move1[i] = 'A'
		p_temp -= power_at(i, powers1)
print(p_max)


n = int(input())
p = list(map(int, input().split()))
s = input()
ans = 0
cur_orig = 0
for i in range(0, n):
	if s[i] == 'B':
		cur_orig += p[i]
cur = cur_orig
ans = cur_orig
for i in range(0, n):
	if s[i] == 'A':
		cur += p[i]
		ans = max(ans, cur)
	else:
		cur -= p[i]
cur = cur_orig
for i in range(n - 1, -1, -1):
	if s[i] == 'A':
		cur += p[i]
		ans = max(ans, cur)
	else:
		cur -= p[i]
print(ans)


n = int(input())
p = [int(x) for x in input().split()]
s = input()
initB = 0
lmax = 0
rmax = 0
curdifl = 0
curdifr = 0
for i in range(n):
	initB += p[i] if s[i] == 'B' else 0
	curdifl += p[i] if s[i] == 'A' else -p[i]
	if curdifl > lmax:
		lmax = curdifl
	curdifr += p[-i - 1] if s[-i - 1] == 'A' else -p[-i - 1]
	if curdifr > rmax:
		rmax = curdifr
print(initB + (max(lmax, rmax) if lmax > 0 or rmax > 0 else 0))


from collections import defaultdict
import bisect
from itertools import accumulate
import os
import sys
import math
from decimal import *
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')
n = int(input())
a = list(map(int, input().split()))
s = input()
ans = 0
cnt = 0
for i in range(0, len(s)):
	if s[i] == 'B':
		ans += a[i]
cnt = ans
fans = ans
for i in range(0, len(s)):
	if s[i] == 'B':
		cnt -= a[i]
	else:
		cnt += a[i]
	fans = max(cnt, fans)
cnt = ans
for i in range(len(s) - 1, -1, -1):
	if s[i] == 'B':
		cnt -= a[i]
	else:
		cnt += a[i]
	fans = max(cnt, fans)
print(fans)


read = lambda : map(int, input().split())
n = int(input())
p = list(read())
a = [{'B': 1, 'A': 0}[i] for i in input()]
cur = sum((p[i] for i in range(n) if a[i]))
ans = cur
b = a[:]
for i in range(n):
	b[i] = int(not a[i])
	if b[i]:
		cur += p[i]
	else:
		cur -= p[i]
	ans = max(ans, cur)
cur = sum((p[i] for i in range(n) if a[i]))
b = a[:]
for i in range(n - 1, -1, -1):
	b[i] = int(not a[i])
	if b[i]:
		cur += p[i]
	else:
		cur -= p[i]
	ans = max(ans, cur)
print(ans)


def cnt(step):
	(temp_total, ans) = (total, 0)
	for i in range(N)[::step]:
		if chars[i] == 'A':
			temp_total += strengths[i]
		else:
			temp_total -= strengths[i]
		ans = max(temp_total, ans)
	return ans
N = int(input())
strengths = [int(_) for _ in input().split()]
chars = list(input())
total = 0
for (i, c) in enumerate(chars):
	if c == 'B':
		total += strengths[i]
print(max([total, cnt(1), cnt(-1)]))


import itertools
g = itertools.accumulate
n = int(input())
strengths = [int(num) for num in input().split()]
teams = input()
indexes = [num for num in range(n)]
s2 = [strengths[i] if teams[i] == 'B' else 0 for i in indexes]
v = [a - 2 * b for (a, b) in zip(strengths, s2)]
b = sum(s2)
result = b + max(0, max(g(v)), max(g(v[::-1])))
print(result)


n = int(input())
prices = list(map(int, input().split()))
who = input()
basic = 0
for i in range(len(who)):
	if who[i] == 'B':
		basic += prices[i]
max = basic
now = basic
for i in range(len(who)):
	if who[i] == 'A':
		now += prices[i]
	else:
		now -= prices[i]
	if now > max:
		max = now
now = basic
for i in range(len(who) - 1, -1, -1):
	if who[i] == 'A':
		now += prices[i]
	else:
		now -= prices[i]
	if now > max:
		max = now
print(max)


n = int(input())
strength = list(map(int, input().split()))
pieces = input()
bob = 0
for (pos, p) in enumerate(pieces):
	if p == 'B':
		bob += strength[pos]
best_flip = 0
cur_flip = 0
for (st, p) in zip(strength, pieces):
	if p == 'A':
		cur_flip += st
	else:
		cur_flip -= st
	best_flip = max(best_flip, cur_flip)
cur_flip = 0
for (st, p) in zip(reversed(strength), reversed(pieces)):
	if p == 'A':
		cur_flip += st
	else:
		cur_flip -= st
	best_flip = max(best_flip, cur_flip)
print(bob + best_flip)


n = int(input())
p = list(map(int, input().split()))
s = input()
total = 0
for i in range(n):
	if s[i] == 'B':
		total += p[i]
ans = total
cur = total
for i in range(n):
	if s[i] == 'A':
		cur += p[i]
	else:
		cur -= p[i]
	ans = max(ans, cur)
cur = total
for i in reversed(range(n)):
	if s[i] == 'A':
		cur += p[i]
	else:
		cur -= p[i]
	ans = max(ans, cur)
print(ans)


n = int(input())
p = list(map(int, input().split()))
l = input()
change = 0
max_change = 0
init_str = 0
for i in range(len(l)):
	if l[i] == 'A':
		change += p[i]
	else:
		change -= p[i]
		init_str += p[i]
	if max_change < change:
		max_change = change
max_change_back = 0
change = 0
for i in range(len(l) - 1, -1, -1):
	if l[i] == 'A':
		change += p[i]
	else:
		change -= p[i]
	if max_change_back < change:
		max_change_back = change
print(max(max_change_back, max_change) + init_str)


n = int(input())
P = list(map(int, input().split()))
S = list(input())
a_sum = 0
b_sum = 0
for i in range(n):
	if S[i] == 'A':
		a_sum += P[i]
	else:
		b_sum += P[i]
max_b = b_sum
b_sum_copy = b_sum
for i in range(n):
	if S[i] == 'A':
		b_sum += P[i]
	else:
		b_sum -= P[i]
	max_b = max(max_b, b_sum)
b_sum = b_sum_copy
for i in range(n - 1, -1, -1):
	if S[i] == 'A':
		b_sum += P[i]
	else:
		b_sum -= P[i]
	max_b = max(max_b, b_sum)
print(max_b)


n = int(input())
P = list(map(int, input().split()))
s = input()
res = sum((P[i] for i in range(n) if s[i] == 'B'))
maxdiff = 0
suma = 0
sumb = 0
for i in range(n):
	if s[i] == 'A':
		suma += P[i]
	else:
		sumb += P[i]
	if suma - sumb > maxdiff:
		maxdiff = suma - sumb
suma = 0
sumb = 0
for i in range(n)[::-1]:
	if s[i] == 'A':
		suma += P[i]
	else:
		sumb += P[i]
	if suma - sumb > maxdiff:
		maxdiff = suma - sumb
print(res + maxdiff)


n = int(input())
p = list(map(int, input().split()))
s = input()
streng = 0
for i in range(0, len(s)):
	if s[i] == 'B':
		streng += p[i]
b = 0
a = 0
ans = streng
for i in range(0, len(s)):
	if s[i] == 'B':
		b += p[i]
	else:
		a += p[i]
	curStren = streng - b + a
	if curStren > ans:
		ans = curStren
a = 0
b = 0
for i in range(1, len(s) + 1):
	if s[-i] == 'B':
		b += p[-i]
	else:
		a += p[-i]
	curStren = streng - b + a
	if curStren > ans:
		ans = curStren
print(ans)


n = int(input())
p = list(map(int, input().split()))
s = input()
ogmx = 0
premx = [0] * (n + 1)
sufmx = [0] * (n + 1)
for i in range(n):
	if s[i] == 'B':
		ogmx += p[i]
premx[0] = ogmx
for i in range(n):
	if s[i] == 'B':
		premx[i + 1] = premx[i] - p[i]
	elif s[i] == 'A':
		premx[i + 1] = premx[i] + p[i]
sufmx[n] = ogmx
for i in range(n - 1, -1, -1):
	if s[i] == 'B':
		sufmx[i] = sufmx[i + 1] - p[i]
	elif s[i] == 'A':
		sufmx[i] = sufmx[i + 1] + p[i]
print(max(max(premx), max(sufmx)))


(n, t) = (int(input()), list(map(int, input().split())))
b = [q * (d == 'B') for (q, d) in zip(t, input())]
v = sum(b)
u = sum(t) - v
s = max(u, v)
for (i, j) in zip(b, t):
	u += 2 * i - j
	v += j - 2 * i
	s = max(u, v, s)
print(s)


n = int(input())
A = list(map(int, input().split()))
b = input()
ans = 0
per = 0
start = 0
for i in range(n):
	if b[i] == 'B':
		start += A[i]
for i in range(n):
	if b[i] == 'A':
		per += A[i]
	else:
		per -= A[i]
	ans = max(per, ans)
per = 0
for i in range(n - 1, -1, -1):
	if b[i] == 'A':
		per += A[i]
	else:
		per -= A[i]
	ans = max(per, ans)
print(start + ans)


def f(n, parr, assign):
	total = 0
	for i in range(n):
		total = total + parr[i] if assign[i] == 'B' else total
	max_v = total
	copy_total = total
	for i in range(n):
		if assign[i] == 'A':
			total += parr[i]
		else:
			total -= parr[i]
		max_v = max(max_v, total)
	total = copy_total
	for i in range(n - 1, -1, -1):
		if assign[i] == 'A':
			total += parr[i]
		else:
			total -= parr[i]
		max_v = max(max_v, total)
	print(max_v)
n = int(input())
parr = [int(v) for v in input().split(' ')]
assign = input()
f(n, parr, assign)


N = int(input())
P = list(map(int, input().split()))
S = input()
S = [0 if S[i] == 'A' else 1 for i in range(N)]
res = strength = sum((P[i] * S[i] for i in range(N)))
for i in range(N):
	strength += (-1) ** S[i] * P[i]
	res = max(res, strength)
strength = sum((P[i] * S[i] for i in range(N)))
for i in range(N)[::-1]:
	strength += (-1) ** S[i] * P[i]
	res = max(res, strength)
print(res)


import sys
input = sys.stdin.readline
n = int(input())
nums = list(map(int, input().split()))
cat = input()
qot = 0
for i in range(n):
	if cat[i] == 'A':
		nums[i] *= -1
	else:
		qot += nums[i]
prefix = [nums[0]]
for i in range(1, n):
	prefix.append(prefix[i - 1] + nums[i])
nums.reverse()
suffix = [nums[0]]
for i in range(1, n):
	suffix.append(suffix[i - 1] + nums[i])
pre = min(prefix)
suf = min(suffix)
presuf = min(pre, suf)
if presuf < 0:
	qot -= presuf
	print(qot)
else:
	print(qot)


n = int(input())
powers = [int(i) for i in input().split()]
teams = input()
org_power = 0
for i in range(n):
	if teams[i] == 'B':
		org_power += powers[i]
(max_power, power) = (org_power, org_power)
for i in range(n):
	if teams[i] == 'A':
		power += powers[i]
		max_power = max(max_power, power)
	else:
		power -= powers[i]
power = org_power
for i in range(n - 1, -1, -1):
	if teams[i] == 'A':
		power += powers[i]
		max_power = max(max_power, power)
	else:
		power -= powers[i]
print(max_power)


(n, p) = (int(input()) + 1, [0] + list(map(int, input().split())))
s = '_' + input()
ans = sum((p[i] for i in range(n) if s[i] == 'B'))
f1 = [0]
for i in range(1, n):
	f1.append(f1[-1] + (0 if s[i] == 'A' else p[i]))
f1 += [0]
f2 = [0]
for i in reversed(range(1, n)):
	f2.append(f2[-1] + (0 if s[i] == 'A' else p[i]))
f2 += [0]
f2.reverse()
ac = 0
for i in range(1, n):
	if s[i] == 'A':
		ac += p[i]
	ans = max(ans, ac + f2[i + 1])
ac = 0
for i in reversed(range(1, n)):
	if s[i] == 'A':
		ac += p[i]
	ans = max(ans, ac + f1[i - 1])
print(ans)


n = int(input())
L = list(map(int, input().split()))
s = input()
prefixe = [None for i in range(n)]
suffixe = [None for i in range(n)]
sumA = 0
sumB = 0
for i in range(n):
	if s[i] == 'B':
		sumB += L[i]
	else:
		sumA += L[i]
sum = max(sumA, sumB)
for i in range(n):
	if s[i] == 'A':
		sumA -= L[i]
		sumB += L[i]
	else:
		sumA += L[i]
		sumB -= L[i]
	sum = max(sum, max(sumA, sumB))
print(sum)


n = int(input())
p = list(map(int, input().split()))
s = input()
ans = bob1 = bob2 = 0
for i in range(n):
	if s[i] == 'B':
		ans += p[i]
		bob1 += p[i]
		bob2 += p[i]
for i in range(n):
	if s[i] == 'A':
		bob1 += p[i]
	else:
		bob1 -= p[i]
	ans = max(ans, bob1)
for i in reversed(range(n)):
	if s[i] == 'A':
		bob2 += p[i]
	else:
		bob2 -= p[i]
	ans = max(ans, bob2)
print(ans)


n = int(input())
p = list(map(int, input().split()))
s = input()
a = [0]
b = [0]
for i in range(n):
	if s[i] == 'A':
		a.append(a[-1] + p[i])
		b.append(b[-1])
	else:
		b.append(b[-1] + p[i])
		a.append(a[-1])
rs = 0
for i in range(1, n + 1):
	rs = max(rs, a[n] - a[i] + b[i], b[n] - b[i] + a[i])
print(rs)


maxChange = 0
n = int(input())
strList = list(map(int, input().split()))
assignment = input()
currStr = 0
changeStrPre = 0
changeStrSuf = 0
for x in range(n):
	if assignment[x] == 'B':
		currStr += strList[x]
		changeStrPre -= strList[x]
	else:
		changeStrPre += strList[x]
		maxChange = max(maxChange, changeStrPre)
	if assignment[n - 1 - x] == 'B':
		changeStrSuf -= strList[n - 1 - x]
	else:
		changeStrSuf += strList[n - 1 - x]
		maxChange = max(maxChange, changeStrSuf)
print(currStr + maxChange)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import Counter
n = int(input())
arr = list(map(int, input().split()))
s = input()
t = 0
for i in range(n):
	if s[i] == 'B':
		t += arr[i]
var = t
m = t
for i in range(n):
	if s[i] == 'A':
		t += arr[i]
	else:
		t -= arr[i]
	m = max(m, t)
for j in range(n - 1, -1, -1):
	if s[j] == 'A':
		var += arr[j]
	else:
		var -= arr[j]
	m = max(m, var)
print(m)


n = int(input())
ps = list(map(int, input().split()))
qs = input()
B = 0
for i in range(n):
	if qs[i] == 'B':
		B += ps[i]
maxi = B
b = B
for i in range(n):
	if qs[i] == 'A':
		b += ps[i]
	elif qs[i] == 'B':
		b -= ps[i]
	maxi = max(maxi, b)
b = B
for i in range(n - 1, -1, -1):
	if qs[i] == 'A':
		b += ps[i]
	elif qs[i] == 'B':
		b -= ps[i]
	maxi = max(maxi, b)
print(maxi)


n = int(input())
a = list(map(int, input().split()))
s = input()
l = 0
b = []
for i in range(n):
	if s[i] == 'B':
		l += a[i]
p = 0
b.append(l)
for i in range(n):
	if s[i] == 'B':
		l = l - a[i]
	else:
		p += a[i]
	b.append(l + p)
l = 0
for i in range(n):
	if s[i] == 'B':
		l += a[i]
p = 0
for i in range(n - 1, -1, -1):
	if s[i] == 'B':
		l = l - a[i]
	else:
		p += a[i]
	b.append(l + p)
print(max(b))


from itertools import accumulate
import math
n = int(input())
p = [int(x) for x in input().split()]
S1 = sum(p)
d = [x == 'A' for x in input()]
for i in range(n):
	if d[i]:
		p[i] = -p[i]
prefix = list(accumulate([0] + p))
S = prefix[-1]
(m, M) = (min(prefix), max(prefix))
print((S1 + max(S - 2 * m, 2 * M - S)) // 2)


n = int(input())
l = [int(i) for i in input().split()]
s = list(input())
sm = 0
for i in range(n):
	if s[i] == 'B':
		sm += l[i]
		l[i] = -l[i]
maxi1 = 0
sm1 = 0
for i in range(n):
	sm1 += l[i]
	maxi1 = max(maxi1, sm1)
sm2 = 0
maxi2 = 0
for i in range(n - 1, -1, -1):
	sm2 += l[i]
	maxi2 = max(maxi2, sm2)
print(sm + max(maxi1, maxi2))


from functools import cmp_to_key
from collections import deque, Counter
from heapq import heappush, heappop
from math import log, ceil
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def ii():
	return int(inp())

def si():
	return str(inp())

def li(lag=0):
	l = list(map(int, inp().split()))
	if lag != 0:
		for i in range(len(l)):
			l[i] += lag
	return l

def mi(lag=0):
	matrix = list()
	for i in range(n):
		matrix.append(li(lag))
	return matrix

def lsi():
	return list(map(str, inp().split()))

def print_list(lista, space=' '):
	print(space.join(map(str, lista)))

def bisect_left(a, x):
	left = 0
	right = len(a)
	while left < right:
		mid = (left + right) // 2
		if a[mid] < x:
			left = mid + 1
		else:
			right = mid
	return left

def bisect_right(a, x):
	left = 0
	right = len(a)
	while left < right:
		mid = (left + right) // 2
		if a[mid] > x:
			right = mid
		else:
			left = mid + 1
	return left

def bisect_elements(a, x):
	return bisect_right(a, x) - bisect_left(a, x)
MOD = 10 ** 9 + 7
maxN = 5
FACT = [0] * maxN
INV_FACT = [0] * maxN

def add(x, y):
	return (x + y) % MOD

def multiply(x, y):
	return x * y % MOD

def power(x, y):
	if y == 0:
		return 1
	elif y % 2:
		return multiply(x, power(x, y - 1))
	else:
		a = power(x, y // 2)
		return multiply(a, a)

def inverse(x):
	return power(x, MOD - 2)

def divide(x, y):
	return multiply(x, inverse(y))

def allFactorials():
	FACT[0] = 1
	for i in range(1, maxN):
		FACT[i] = multiply(i, FACT[i - 1])

def inverseFactorials():
	n = len(INV_FACT)
	INV_FACT[n - 1] = inverse(FACT[n - 1])
	for i in range(n - 2, -1, -1):
		INV_FACT[i] = multiply(INV_FACT[i + 1], i + 1)

def coeffBinom(n, k):
	if n < k:
		return 0
	return multiply(FACT[n], multiply(INV_FACT[k], INV_FACT[n - k]))

def create_graph(n, m, undirected=1, unweighted=1):
	graph = [[] for i in range(n)]
	if unweighted:
		for i in range(m):
			[x, y] = li(lag=-1)
			graph[x].append(y)
			if undirected:
				graph[y].append(x)
	else:
		for i in range(m):
			[x, y, w] = li(lag=-1)
			w += 1
			graph[x].append([y, w])
			if undirected:
				graph[y].append([x, w])
	return graph

def create_tree(n, unweighted=1):
	children = [[] for i in range(n)]
	if unweighted:
		for i in range(n - 1):
			[x, y] = li(lag=-1)
			children[x].append(y)
			children[y].append(x)
	else:
		for i in range(n - 1):
			[x, y, w] = li(lag=-1)
			w += 1
			children[x].append([y, w])
			children[y].append([x, w])
	return children

def dist(tree, n, A, B=-1):
	s = [[A, 0]]
	(massimo, massimo_nodo) = (0, 0)
	distanza = -1
	v = [-1] * n
	while s:
		(el, dis) = s.pop()
		if dis > massimo:
			massimo = dis
			massimo_nodo = el
		if el == B:
			distanza = dis
		for child in tree[el]:
			if v[child] == -1:
				v[child] = 1
				s.append([child, dis + 1])
	return (massimo, massimo_nodo, distanza)

def diameter(tree):
	(_, foglia, _) = dist(tree, n, 0)
	(diam, _, _) = dist(tree, n, foglia)
	return diam

def dfs(graph, n, A):
	v = [-1] * n
	s = [[A, 0]]
	v[A] = 0
	while s:
		(el, dis) = s.pop()
		for child in graph[el]:
			if v[child] == -1:
				v[child] = dis + 1
				s.append([child, dis + 1])
	return v

def bfs(graph, n, A):
	v = [-1] * n
	s = deque()
	s.append([A, 0])
	v[A] = 0
	while s:
		(el, dis) = s.popleft()
		for child in graph[el]:
			if v[child] == -1:
				v[child] = dis + 1
				s.append([child, dis + 1])
	return v

def parents_children_root_unrooted_tree(tree, n, root=0):
	q = deque()
	visited = [0] * n
	parent = [-1] * n
	children = [[] for i in range(n)]
	q.append(root)
	while q:
		all_done = 1
		visited[q[0]] = 1
		for child in tree[q[0]]:
			if not visited[child]:
				all_done = 0
				q.appendleft(child)
		if all_done:
			for child in tree[q[0]]:
				if parent[child] == -1:
					parent[q[0]] = child
					children[child].append(q[0])
			q.popleft()
	return (parent, children)

def all_longest_path_passing_from_node(parent, children, n):
	q = deque()
	visited = [len(children[i]) for i in range(n)]
	downwards = [[0, 0] for i in range(n)]
	upward = [1] * n
	longest_path = [1] * n
	for i in range(n):
		if not visited[i]:
			q.append(i)
			downwards[i] = [1, 0]
	while q:
		node = q.popleft()
		if parent[node] != -1:
			visited[parent[node]] -= 1
			if not visited[parent[node]]:
				q.append(parent[node])
		else:
			root = node
		for child in children[node]:
			downwards[node] = sorted([downwards[node][0], downwards[node][1], downwards[child][0] + 1], reverse=True)[0:2]
	s = [node]
	while s:
		node = s.pop()
		if parent[node] != -1:
			if downwards[parent[node]][0] == downwards[node][0] + 1:
				upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][1])
			else:
				upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][0])
		longest_path[node] = downwards[node][0] + downwards[node][1] + upward[node] - min([downwards[node][0], downwards[node][1], upward[node]]) - 1
		for child in children[node]:
			s.append(child)
	return longest_path
n = ii()
p = li()
c = si()
v = []
for i in range(n):
	if c[i] == 'B':
		v.append(-p[i])
	else:
		v.append(p[i])
s = 0
for i in range(n):
	if c[i] == 'B':
		s += p[i]
ac = 0
mac = 0
for i in range(n):
	ac += v[i]
	mac = max(ac, mac)
ac = 0
for i in range(n):
	ac += v[n - 1 - i]
	mac = max(ac, mac)
print(s + mac)