3074: Find Maximum
Time Limit: 2 Sec Memory Limit: 256 MBSubmit: 0 Solved: 0
[Submit] [Status] [Web Board] [Creator:]
Description
Valera has array a, consisting of n integers a0,a1,...,an-1, and function f(x), taking an integer from 0 to 2n-1 as its single argument. Value f(x) is calculated by formula 
, 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=20+21+23), then f(x)=a0+a1+a3.
Help Valera find the maximum of function f(x) among all x, for which an inequality holds: 0≤x≤m.
The first line contains integer n (1≤n≤105) − the number of array elements. The next line contains n space-separated integers a0,a1,...,an-1 (0≤ai≤104) − elements of array a.
The third line contains a sequence of digits zero and one without spaces s0s1... sn-1 − the binary representation of number m. Number m equals 
.
Print a single integer − the maximum value of function f(x) for all 
.
2
3 8
10
3
5
17 0 10 2 1
11010
27
In the first test case m=20=1,f(0)=0,f(1)=a0=3.
In the second sample m=20+21+23=11, the maximum value of function equals f(5)=a0+a2=17+10=27.