#P353C. Find Maximum
-
ID: 2801
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Find Maximum
No submission language available for this problem.
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 
.
Input
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 .
Output
Print a single integer — the maximum value of function f(x) for all .
Samples
2
3 8
10
3
5
17 0 10 2 1
11010
27
Note
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.