No tag edit access

C. Find Maximum

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputValera 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 , 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*_{0}*s*_{1}... *s*_{n - 1} — the binary representation of number *m*. Number *m* equals .

Output

Print a single integer — the maximum value of function *f*(*x*) for all .

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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/21/2018 11:03:44 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|