Valera has array a, consisting of n integers a_0, a_1, ..., a_{n} - 1, and function f(x), taking an integer from 0 to 2^{n} - 1 as its single argument. Value f(x) is calculated by formula $f(x) = \sum_{i = 0}^{n - 1} a_{i} \cdot b i t(i)$, where value bit(i) equals one if the binary representation of number x contains a 1 on the i-th position, and zero otherwise.

For example, if n = 4 and x = 11 (11 = 2^0 + 2^1 + 2^3), then f(x) = a_0 + a_1 + a_3.

Help Valera find the maximum of function f(x) among all x, for which an inequality holds: 0 ≤ x ≤ m.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5) — the number of array elements. The next line contains n space-separated integers a_0, a_1, ..., a_{n} - 1 (0 ≤ a_{i} ≤ 10^4) — elements of array a.

The third line contains a sequence of digits zero and one without spaces s_0s_1... s_{n} - 1 — the binary representation of number m. Number m equals $\sum_{i = 0}^{n - 1} 2^{i} \cdot s_{i}$.


-----Output-----

Print a single integer — the maximum value of function f(x) for all $x \in [ 0 . . m ]$.


-----Examples-----
Input
2
3 8
10

Output
3

Input
5
17 0 10 2 1
11010

Output
27



-----Note-----

In the first test case m = 2^0 = 1, f(0) = 0, f(1) = a_0 = 3.

In the second sample m = 2^0 + 2^1 + 2^3 = 11, the maximum value of function equals f(5) = a_0 + a_2 = 17 + 10 = 27.

Difficulty: MEDIUM_HARD
Tags: Mathematics

Number theory

Implementation

Starter code:

Solutions:
m = int(input())
listValue = input().split()
x = input().rstrip('\n')
values = [int(v) for v in listValue]
reverse_x = list(x)
reverse_int = [int(s) for s in reverse_x]
reverse_list = [0] * m
sum_list = 0
for i in range(m):
	if reverse_x[i] == '1':
		reverse_list[i] = max(reverse_list[i - 1] + values[i], sum_list)
	else:
		reverse_list[i] = reverse_list[i - 1]
	sum_list += values[i]
print(reverse_list[-1])


n = int(input())
a = list(map(int, input().split()))
m = input()
(res, summ) = (0, 0)
for (i, bit) in enumerate(m):
	if bit == '1':
		res = max(res + a[i], summ)
	summ += a[i]
print(res)


n = int(input())
s = list(map(int, input().split()))
bit = input()
(res, m) = (0, 0)
for i in range(len(bit)):
	if bit[i] == '1':
		res = max(s[i] + res, m)
	m += s[i]
print(res)


import math
import random
from queue import Queue
import time

def main(arr, m):
	m = list(reversed(m))
	arr = list(reversed(arr))
	start = sum(arr)
	possible_ans = []
	l = 0
	for i in range(len(arr)):
		if m[i] == '0':
			start -= arr[i]
		else:
			l += arr[i]
			if start - arr[i] > arr[i]:
				possible_ans.append(start - arr[i])
	possible_ans.append(l)
	return max(possible_ans)
n = int(input())
arr = list(map(int, input().split()))
m = input()
print(main(arr, m))


import sys
from math import gcd, sqrt, ceil, log2
from collections import defaultdict, Counter, deque
from bisect import bisect_left, bisect_right
import math
import heapq
from itertools import permutations
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')

def get_sum(bit, i):
	s = 0
	i += 1
	while i > 0:
		s += bit[i]
		i -= i & -i
	return s

def update(bit, n, i, v):
	i += 1
	while i <= n:
		bit[i] += v
		i += i & -i

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def primeFactors(n):
	sa = set()
	sa.add(n)
	while n % 2 == 0:
		sa.add(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			sa.add(i)
			n = n // i
	return sa

def seive(n):
	pri = [True] * (n + 1)
	p = 2
	while p * p <= n:
		if pri[p] == True:
			for i in range(p * p, n + 1, p):
				pri[i] = False
		p += 1
	return pri

def check_prim(n):
	if n < 0:
		return False
	for i in range(2, int(sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True

def getZarr(string, z):
	n = len(string)
	(l, r, k) = (0, 0, 0)
	for i in range(1, n):
		if i > r:
			(l, r) = (i, i)
			while r < n and string[r - l] == string[r]:
				r += 1
			z[i] = r - l
			r -= 1
		else:
			k = i - l
			if z[k] < r - i + 1:
				z[i] = z[k]
			else:
				l = i
				while r < n and string[r - l] == string[r]:
					r += 1
				z[i] = r - l
				r -= 1

def search(text, pattern):
	concat = pattern + '$' + text
	l = len(concat)
	z = [0] * l
	getZarr(concat, z)
	ha = []
	for i in range(l):
		if z[i] == len(pattern):
			ha.append(i - len(pattern) - 1)
	return ha

def mergeIntervals(arr):
	arr.sort(key=lambda x: x[0])
	m = []
	s = -10000
	max = -100000
	for i in range(len(arr)):
		a = arr[i]
		if a[0] > max:
			if i != 0:
				m.append([s, max])
			max = a[1]
			s = a[0]
		elif a[1] >= max:
			max = a[1]
	if max != -100000 and [s, max] not in m:
		m.append([s, max])
	return m
n = int(input())
l = list(map(int, input().split()))
l.reverse()
m = input()[::-1]
ans = 0
z = sum(l)
yo = 0
flag = 0
for i in range(n):
	z -= l[i]
	if m[i] == '1':
		ans = max(z + yo, ans)
		yo += l[i]
ans = max(z + yo, ans)
print(ans)


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


n = int(input())
a = list(map(int, input().split()))
s = input()
ans = 0
sm = 0
for i in range(n):
	if s[i] == '1':
		ans = max(ans + a[i], sm)
	sm += a[i]
print(ans)


3

def readln():
	return tuple(map(int, input().split()))
(n,) = readln()
a = readln()
s = [0] * (n + 1)
sm = [0] * (n + 1)
m = list(input())
for i in range(n):
	s[i + 1] = s[i] + a[i]
	sm[i + 1] = sm[i] + (a[i] if m[i] == '1' else 0)
ans = sm[n]
for i in range(n - 1, -1, -1):
	if m[i] == '1':
		ans = max(ans, s[i] + sm[n] - sm[i + 1])
print(ans)


import os
import sys
from math import *
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
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')

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
n = Int()
a = array()
s = input().rstrip('0')
ans = 0
not_included = 0
for i in range(len(s)):
	if s[i] == '0':
		not_included += a[i]
	elif not_included > a[i]:
		ans += not_included
		not_included = a[i]
	else:
		ans += a[i]
print(ans)


def makePref(a):
	pref = a[:]
	for i in range(1, len(pref)):
		pref[i] += pref[i - 1]
	return pref

def makeSuff(a, m):
	suff = a[:]
	for i in range(len(suff)):
		suff[i] *= m[i]
	for i in range(len(suff) - 2, -1, -1):
		suff[i] += suff[i + 1]
	return suff

def solve(pref, suff, m):
	ans = suff[0]
	for i in range(1, len(m)):
		if m[i] == 1:
			if i == len(m) - 1:
				ans = max(ans, pref[i - 1])
			else:
				ans = max(ans, pref[i - 1] + suff[i + 1])
	return ans
n = int(input())
a = [int(x) for x in input().split()]
m = [int(x) for x in input()]
pref = makePref(a)
suff = makeSuff(a, m)
print(solve(pref, suff, m))


n = int(input())
a = list(map(int, input().split(' ')))[::-1]
m = input()[::-1]
sumall = [0] * (n + 1)
for (x, ai) in enumerate(reversed(a)):
	i = n - 1 - x
	sumall[i] = sumall[i + 1] + ai
summ = [0] * (n + 1)
for (i, ai) in enumerate(a):
	summ[i] = summ[i - 1]
	if m[i] == '1':
		summ[i] += ai
maxval = summ[n - 1]
for i in range(n):
	if m[i] == '1' and maxval < summ[i - 1] + sumall[i + 1]:
		maxval = summ[i - 1] + sumall[i + 1]
print(maxval)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def L():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
try:
	sys.stdin = open('input.txt', 'r')
except:
	pass

def pmat(A):
	for ele in A:
		print(*ele, end='\n')

def seive():
	prime = [1 for i in range(10 ** 6 + 1)]
	prime[0] = 0
	prime[1] = 0
	for i in range(10 ** 6 + 1):
		if prime[i]:
			for j in range(2 * i, 10 ** 6 + 1, i):
				prime[j] = 0
	return prime
n = L()[0]
A = L()
m = input()
pref = [0]
prefs = [0]
for i in range(n):
	pref.append(A[i] * int(m[i]) + pref[-1])
	prefs.append(A[i] + prefs[-1])
ans = pref[-1]
pref += [pref[-1]]
prefs += [prefs[-1]]
for i in range(n):
	if m[i] == '0':
		continue
	new = prefs[i] + pref[-2] - pref[i + 1]
	ans = max(new, ans)
print(ans)
endtime = time.time()


N = int(input())
data = [int(i) for i in input().split()]
M = input()
Sgood = [0] * N
Sgood[0] = max(data[0], 0)
for i in range(1, N):
	Sgood[i] = Sgood[i - 1] + max(data[i], 0)
Sorig = [0] * N
Sorig[0] = max(data[0] if M[0] == '1' else 0, 0)
for i in range(1, N):
	Sorig[i] = Sorig[i - 1] + max(data[i] if M[i] == '1' else 0, 0)
answer = Sorig[-1]
for i in range(1, N):
	if M[i] == '1':
		answer = max((answer, Sgood[i - 1] + Sorig[-1] - Sorig[i]))
print(answer)


from sys import stdin, stdout
from itertools import accumulate
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, stdin.readline().split()))
for _ in range(1):
	n = nmbr()
	a = lst()
	s = input()
	norm = [int(s[i]) * a[i] for i in range(n)]
	ans = sum(norm)
	pre = list(accumulate(a))
	suf = list(accumulate(norm))
	for i in range(n):
		if s[i] == '1':
			ans = max(ans, pre[i] - a[i] + (suf[-1] - suf[i]))
	print(ans)


n = int(input())
a = [int(i) for i in input().split()]
m = input()
pos = []
i = n - 1
while i >= 0:
	if m[i] == '1':
		pos.append(i)
	i -= 1
if len(pos) == 0:
	print(0)
else:
	total = 0
	presum = [a[0]]
	for i in range(1, pos[0] + 1):
		presum.append(presum[-1] + a[i])
	r_sum = 0
	for i in range(len(pos)):
		total = max(total, presum[pos[i]] + r_sum - a[pos[i]])
		r_sum += a[pos[i]]
	print(max(total, r_sum))


n = int(input())
a = list(map(int, input().split()))
cum_sum = [0] * (n + 1)
act_sum = [0] * (n + 1)
m = list(input())
for i in range(n):
	cum_sum[i + 1] = cum_sum[i] + a[i]
	act_sum[i + 1] = act_sum[i]
	if m[i] == '1':
		act_sum[i + 1] += a[i]
res = 0
for i in range(n - 1, -1, -1):
	if m[i] == '1':
		res = max(res, cum_sum[i] - act_sum[i + 1])
print(res + act_sum[n])


n = int(input())
a = list(map(int, input().split()))
s = input()
prefix = [0] * n
prefix[0] = a[0]
for i in range(1, n):
	prefix[i] = prefix[i - 1] + a[i]
last = 0
answ = 0
if len(s) > n:
	print(sum(a))
	return
for (i, x) in enumerate(s):
	if x == '1':
		last = i
	answ += a[i] * int(x)
total = 0
for i in range(last, 0, -1):
	if s[i] == '0':
		continue
	answ = max(answ, total + prefix[i - 1])
	total += a[i]
print(answ)


n = int(input())
a = list(map(int, input().split()))
sum = [0] * (n + 1)
sum[1] = a[0]
sum[0] = 0
for i in range(2, n + 1):
	sum[i] = sum[i - 1] + a[i - 1]
s = input()
maxi = 0
cur = n - 1
tmp = 0
while cur >= 0:
	if s[cur] == '1':
		x = sum[cur] + tmp
		if x > maxi:
			maxi = x
		tmp += a[cur]
	cur -= 1
if tmp > maxi:
	maxi = tmp
print(maxi)


from sys import stdin

def main():
	n = int(stdin.readline())
	ar = list(map(int, stdin.readline().split()))
	ar.reverse()
	s = list(input())
	s.reverse()
	pre = [0] * n
	if s[0] == '1':
		pre[0] = ar[0]
	for i in range(1, n):
		if s[i] == '1':
			pre[i] = pre[i - 1] + ar[i]
		else:
			pre[i] = pre[i - 1]
	post = [0] * n
	post[n - 1] = ar[n - 1]
	for i in range(n - 2, -1, -1):
		post[i] = post[i + 1] + ar[i]
	ans = pre[n - 1]
	for i in range(n - 2, -1, -1):
		if s[i] == '1':
			ans = max(ans, pre[i] - ar[i] + post[i + 1])
	print(ans)
main()


import os
import sys
from io import BytesIO, IOBase
from math import log2, ceil, sqrt, gcd, log
from itertools import permutations, combinations
from collections import *
from bisect import *
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')
g = lambda : input().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
rr = lambda x: reversed(range(x))
mod = int(1000000000.0) + 7
inf = float('inf')
(n,) = gil()
a = gil()
s = g()
one = []
ans = 0
b = a[:]
for i in range(n):
	if s[i] == '1':
		one.append(i)
for i in range(1, n):
	a[i] += a[i - 1]
a.append(0)
right = 0
for j in reversed(range(len(one))):
	ans = max(ans, a[one[j] - 1] + right)
	right += b[one[j]]
print(max(ans, right))


import sys

class DFSHelper:
	mxNum = 0
d = DFSHelper()

def backTrack(maxval, curval, binPos, maxBinPos, arr, total):
	if binPos > maxBinPos:
		if maxval >= curval:
			d.mxNum = max(d.mxNum, total)
		return
	nxtVal = (1 << binPos) + curval
	backTrack(maxval, nxtVal, binPos + 1, maxBinPos, arr, total + arr[binPos])
	nxtVal = curval
	backTrack(maxval, nxtVal, binPos + 1, maxBinPos, arr, total)

def constructM(m):
	mult = 0
	total = 0
	for char in m:
		if char == '1':
			total += 2 ** mult
		mult += 1
	return total

def solve(arr, m):
	maxval = constructM(m)
	curval = 0
	binPos = 0
	maxBinPos = len(m) - 1
	backTrack(maxval, curval, binPos, maxBinPos, arr, 0)
	return d.mxNum

def solve2(arr, m):
	DPTable = [[0 for _ in range(3)] for _ in range(len(arr) + 1)]
	for i in range(len(arr)):
		if m[i] == '0':
			DPTable[i + 1][2] = DPTable[i][2]
			DPTable[i + 1][1] = max(DPTable[i][1], DPTable[i][1] + arr[i])
		if m[i] == '1':
			DPTable[i + 1][2] = max(DPTable[i][2] + arr[i], DPTable[i][1])
			DPTable[i + 1][1] = max(DPTable[i][1], DPTable[i][1] + arr[i])
	return DPTable[-1][2]

def readinput():
	n = int(sys.stdin.readline().rstrip())
	arr = list(map(int, sys.stdin.readline().rstrip().split(' ')))
	m = str(sys.stdin.readline().rstrip())
	print(solve2(arr, m))
readinput()


import sys
import string
import math
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache
from fractions import Fraction

def mi(s):
	return map(int, s.strip().split())

def lmi(s):
	return list(mi(s))

def tmi(s):
	return tuple(mi(s))

def mf(f, s):
	return map(f, s)

def lmf(f, s):
	return list(mf(f, s))

def js(lst):
	return ' '.join((str(d) for d in lst))

def jsns(lst):
	return ''.join((str(d) for d in lst))

def line():
	return sys.stdin.readline().strip()

def linesp():
	return line().split()

def iline():
	return int(line())

def mat(n):
	matr = []
	for _ in range(n):
		matr.append(linesp())
	return matr

def matns(n):
	mat = []
	for _ in range(n):
		mat.append([c for c in line()])
	return mat

def mati(n):
	mat = []
	for _ in range(n):
		mat.append(lmi(line()))
	return mat

def pmat(mat):
	for row in mat:
		print(js(row))

def main():
	line()
	arr = lmi(line())
	bits = line()
	curr_best = 0
	bit_sum = {-1: 0}
	for (e, temp) in enumerate(zip(arr, bits)):
		(val, bit) = temp
		if bit == '1':
			curr_best += val
		bit_sum[e] = curr_best
	cum_sum = {-1: 0}
	for (e, n) in enumerate(arr):
		cum_sum[e] = cum_sum[e - 1] + n
	for (e, bit) in enumerate(bits):
		if bit == '1':
			new_best = cum_sum[e - 1] + bit_sum[len(bits) - 1] - bit_sum[e]
			curr_best = max(curr_best, new_best)
	print(curr_best)
main()


from sys import exit
n = int(input())
a = list(map(int, input().split()))
s = input()
prefix = [0] * n
prefix[0] = a[0]
for i in range(1, n):
	prefix[i] = prefix[i - 1] + a[i]
last = 0
answ = 0
if len(s) > n:
	print(sum(a))
	exit(0)
for (i, x) in enumerate(s):
	if x == '1':
		last = i
	answ += a[i] * int(x)
total = 0
for i in range(last, 0, -1):
	if s[i] == '0':
		continue
	answ = max(answ, total + prefix[i - 1])
	total += a[i]
print(answ)


n = int(input())
a = list(map(int, input().split()))
k = input()
pref = [a[0]]
for i in range(1, n):
	pref.append(pref[-1] + a[i])
cur = 0
ans = 0
for i in range(n - 1, -1, -1):
	if k[i] == '0':
		continue
	if cur + (pref[i - 1] if i > 0 else 0) > ans:
		ans = cur + (pref[i - 1] if i > 0 else 0)
	cur += a[i]
cur = 0
for i in range(n):
	if k[i] == '1':
		cur += a[i]
ans = max(ans, cur)
print(ans)


import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
Sums = [0] * N
m = sys.stdin.readline()
maxx = 0
s = 0
for i in range(N):
	s += A[i]
	Sums[i] = s
	if m[i] == '1':
		maxx += A[i]
ind = N - 1
for i in range(N):
	if m[i] != '1':
		ind = i
		break
temp_ans = 0
conf = ''
for i in range(N - 1, 0, -1):
	if i == ind:
		break
	if m[i] == '1':
		temp_ans += A[i]
		if A[i] < Sums[i - 1]:
			ans = temp_ans - A[i] + Sums[i - 1]
			if ans > maxx:
				maxx = ans
print(maxx)


n = int(input())
a = list(map(int, input().split()))
s = input()
m = len(s)
prevSum = [0] * n
prevSum[0] = a[0]
for i in range(1, n):
	prevSum[i] = prevSum[i - 1] + a[i]
dp = [0] * m
lastOne = -1
if s[0] != '0':
	lastOne = 0
	dp[0] = a[0]
for i in range(1, m):
	if s[i] == '0':
		dp[i] = dp[i - 1]
	else:
		y = 0
		if lastOne != -1:
			y = dp[lastOne]
		dp[i] = max(prevSum[i - 1], y + a[i])
		lastOne = i
print(dp[m - 1])


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
n = int(input())
s = list(map(int, input().split()))
bit = input()
(res, m) = (0, 0)
for i in range(len(bit)):
	if bit[i] == '1':
		res = max(s[i] + res, m)
	m += s[i]
print(res)


import bisect
from itertools import accumulate, count
import os
import sys
import math
from decimal import *
from io import BytesIO, IOBase
from sys import maxsize
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')

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def SieveOfEratosthenes(n):
	prime = []
	primes = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if primes[p] == True:
			prime.append(p)
			for i in range(p * p, n + 1, p):
				primes[i] = False
		p += 1
	return prime

def primefactors(n):
	fac = []
	while n % 2 == 0:
		fac.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 2):
		while n % i == 0:
			fac.append(i)
			n = n // i
	if n > 1:
		fac.append(n)
	return sorted(fac)

def factors(n):
	fac = set()
	fac.add(1)
	fac.add(n)
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			fac.add(i)
			fac.add(n // i)
	return list(fac)

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
n = int(input())
a = list(map(int, input().split()))
s = input()
ans = 0
fans = 0
for i in range(0, len(s)):
	if s[i] == '1':
		ans = max(ans + a[i], fans)
	fans += a[i]
print(ans)


n = int(input())
a = list(list(map(int, input().split())))
m = input()
s = [int(i) for i in m]
max = 0
sum = 0
for k in range(n):
	sum += a[k] * s[k]
if sum > max:
	max = sum
for i in range(1, n):
	p = s[i]
	q = s[i - 1]
	if p and q == 0:
		sum -= a[i]
		s[i] = 0
		for j in range(i - 1, -1, -1):
			if s[j]:
				break
			sum += a[j]
			s[j] = 1
		if sum > max:
			max = sum
print(max)


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
s = list(input().rstrip())
for i in range(len(s)):
	s[i] = int(s[i])
(ans, x) = (0, 0)
for i in range(n):
	if s[i] == 1:
		ans = max(ans + a[i], x)
	x += a[i]
print(ans)


n = int(input())
a = list(map(int, input().split()))
c = input()
(o, k) = (0, 0)
dp = []
for i in range(n):
	e = int(c[i])
	if e:
		if a[i] > k:
			o = o + a[i]
		else:
			o = o + k
			k = a[i]
	k = k + (1 - e) * a[i]
print(o)


def main():
	n = int(input())
	a = list(map(int, input().split()))
	k = input()
	(ans, s) = (0, 0)
	for i in range(n):
		if k[i] == '1':
			ans = max(ans + a[i], s)
		s += a[i]
	print(ans)

def __starting_point():
	main()
__starting_point()


from sys import stdin
from itertools import accumulate

def arr_enu():
	return [[i, int(x)] for (i, x) in enumerate(stdin.readline().split())]

def get_col(arr, i):
	return [row[i] for row in arr]

def arr_sum(arr):
	arr.insert(0, 0)
	return list(accumulate(arr, lambda x, y: x + y))

def fun(x, y):
	return int(x) * y[1]
(n, a, s) = (int(stdin.readline()), arr_enu(), stdin.readline())
(cum, cum2) = (arr_sum(get_col(a, 1)), arr_sum(list(map(fun, s, a))))
ans = cum2[-1]
for i in range(n - 1, -1, -1):
	if s[i] == '1':
		ans = max(ans, cum[i] + (cum2[-1] - cum2[i + 1]))
print(ans)


def main():
	input()
	a = [int(c) for c in input().split()]
	s = list(input())
	sum_ = ans = 0
	for (a_i, s_i) in zip(a, s):
		if s_i == '1':
			ans = max(ans + a_i, sum_)
		sum_ += a_i
	print(ans)
main()


n = int(input())
a = input().split()
s = input()
if '1' not in s:
	print(0)
else:
	ls = [0 for i in range(n)]
	prefix = [0 for i in range(n)]
	valid = [0 for i in range(n)]
	for i in range(n):
		if i == 0:
			if s[i] == '1':
				ls[0] = int(a[i])
				valid[i] = 1
			prefix[0] = int(a[i])
		else:
			if s[i] == '1':
				ls[i] = ls[i - 1] + int(a[i])
				valid[i] = 1
			else:
				ls[i] = ls[i - 1]
			prefix[i] = prefix[i - 1] + int(a[i])
	new_ls = [ls[n - 1]]
	for i in range(1, n):
		if valid[i]:
			new_ls.append(prefix[i - 1] + ls[n - 1] - ls[i])
	print(max(new_ls))


n = int(input())
elems = [int(i) for i in input().split()]
acum = []
acum.append(elems[0])
for i in range(1, n):
	acum.append(elems[i] + acum[i - 1])
m = input()
dp = [0 for i in range(n)]
dp[0] = elems[0] * int(m[0])
for i in range(1, n):
	dp[i] = dp[i - 1] + elems[i] * int(m[i])
	if m[i] == '1':
		dp[i] = max(dp[i], acum[i - 1])
print(dp[n - 1])


n = int(input())
a = list(map(int, input().split()))
b = [0] + a
for i in range(1, n + 1):
	b[i] += b[i - 1]
t = input()
(s, m, i) = (0, 0, t.rfind('1'))
while i >= 0:
	d = b[i] + s
	if d > m:
		m = d
	if d + a[i] < m:
		break
	s += a[i]
	i = t[:i].rfind('1')
print(max(m, s))


from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict
from bisect import bisect_left
n = int(stdin.readline().strip())
arr = list(map(int, stdin.readline().split()))
barr = list(stdin.readline().strip())
prefix = [0] * n
prefix[0] = arr[0]
for i in range(1, n):
	prefix[i] = prefix[i - 1] + arr[i]
mx = 0
temp = 0
for i in range(n - 1, -1, -1):
	if barr[i] == '1':
		if i >= 1:
			mx = max(mx, temp + prefix[i - 1])
		temp += arr[i]
mx = max(mx, temp)
print(mx)