Valera 有数组 a,由 n 个整数 a0、a1、...、an - 1 和函数 f(x) 组成,函数 f(x) 以 0 到 2n - 1 之间的整数作为其单个参数。值 f(x) 通过公式 $$f(x) = \sum_{i=0}^{n-1} a_i \cdot bit(i)$$ 计算,其中如果数字 x 的二进制表示形式在第 i 个位置包含 1,则值 bit(i) 等于 1,否则为零。
例如,如果 n = 4 且 x = 11 (11 = 20 + 21 + 23),则 f(x) = a0 + a1 + a3。
帮助 Valera 找到所有 x 中函数 f(x) 的最大值,其中不等式成立:0 ≤ x ≤ m。
输入
第一行包含整数 n (1 ≤ n ≤ 105) — 数组元素的数量。下一行包含 n 个空格分隔的整数 a0, a1, ..., an - 1 (0 ≤ ai ≤ 104) — 数组 a 的元素。
第三行包含数字 0 和 1 的序列,不带空格 s0s1... sn - 1 — 数字 m 的二进制表示形式。数字 m 等于 $$\sum_{i=0}^{n-1} 2^i \cdot s_i$$。
输出
打印单个整数 — [0..m]$$ 中所有 $$x 的函数 f(x) 的最大值。
示例
输入 #1
2 3 8 10
输出 #1
3
输入 #2
5 17 0 10 2 1 11010
输出 #2
27
注意
在第一个测试用例中,m = 20 = 1,f(0) = 0,f(1) = a0 = 3。
在第二个样本 m = 20 + 21 + 23 = 11 中,函数的最大值等于 f(5) = a0 + a2 = 17 + 10 = 27。