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: interview

Starter code:

Solutions:
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)


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)        



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)


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()))
m = input()

res, summ = 0, 0

for i, bit in enumerate(m):
    if bit == '1':
        res = max(res + a[i], summ) # try to add
    summ += a[i]

print(res)

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()))
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))

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)


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)

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)

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)




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(" ")))[::-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)


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) # try to add

    summ += a[i]



print(res)



# Made By Mostafa_Khaled


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)

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])



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()

'''input
2
3 8
10
'''
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict
from bisect import bisect_left

# main starts
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]
	# print(temp, mx)
mx = max(mx, temp)
print(mx)


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)

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)


def __starting_point():
    main()
__starting_point()

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)


def __starting_point():
    main()
__starting_point()

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))        

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)


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()
ans, S = 0, 0

for i in range(n):
  if s[i] == '1':
    ans = max(ans + a[i], S)
  S += a[i]
print(ans)