| Codeforces Round 205 (Div. 2) |
|---|
| Закончено |
У Валеры имеется массив a, состоящий из n целых чисел a0, a1, ..., an - 1, и функция f(x) принимающая в качестве своего единственного аргумента целое число от 0 до 2n - 1. Значение f(x) считается по формуле 
, где значение bit(i) равно единице, если в двоичном представлении числа x в i-ой позиции стоит 1, или нулю в противном случае.
Например, если n = 4, а x = 11 (11 = 20 + 21 + 23), тогда f(x) = a0 + a1 + a3.
Помогите Валере найти максимум функции f(x) среди всех x, для которых выполняется неравенство: 0 ≤ x ≤ m.
В первой строке записано целое число n (1 ≤ n ≤ 105) — количество элементов массива. В следующей строке через пробел записаны n целых чисел a0, a1, ..., an - 1 (0 ≤ ai ≤ 104) — элементы массива a.
В третьей строке записана последовательность нулей и единиц без пробелов s0s1... sn - 1 — двоичное представление числа m. Число m равно 
.
Выведите единственное целое число — максимальное значение функции f(x) среди всех 
.
2
3 8
10
3
5
17 0 10 2 1
11010
27
В первом тестовом примере m = 20 = 1, f(0) = 0, f(1) = a0 = 3.
Во втором примере m = 20 + 21 + 23 = 11, а максимальное значение функции равно f(5) = a0 + a2 = 17 + 10 = 27.
