(SENIOR) The Math question

All submissions for this problem are available.
Piyush has array a, consisting of n integers a_{0},a_{1}a_{2},a_{n1}, 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 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 Piyush find the miximum of the function f(x) among all x, for which an equality holds: 0 ≤ x ≤ m .
Input
 The first line contains integer T the number of test cases.
 For each test case, the first line contains n the number of array elements. The next line contains n space separated integers a_{0},a_{1},a_{2}...a_{n1} the elements of array a.
 The next line contains a sequence of digits zero and one without spaces s_{0},s_{1},...,s_{n1} the binary representation of number m. Number m equals .
Output
 For each test case print a single  integer the maximum value of f(x) for all x ∈[0...m].
Constraints
 1 ≤ T ≤ 50
 1 ≤ n ≤ 10^{5}
 0 ≤ a_{i} ≤ 10^{4}.
Example
Input: 2 2 3 8 10 5 17 0 10 2 1 11010 Output: 3 27
Explanation
 In the first test case m=2^{0}=1, f(0)=0, f(1)=a_{0} =3.
 In the second test case m= 2^{0} + 2^{1} + 2^{3} =11, the maximum value of function equals f(5) = a_{0} + a_{2} = 17 + 10 =17.
Author:  palash117 
Tags  palash117 
Date Added:  26022015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 