Giá trị lớn nhất của hàm bit

Cho mảng $a$ gồm $n$ số nguyên không âm $a_0,a_1,\dots ,a_{n-1}$ và hàm $f$ nhận vào một số nguyên $x$ với $0\le x\le 2^n-1$, được định nghĩa như sau:

$$f(x)=\sum _{i=0}^{n-1}{a}_i·\text{bit}(i)$$

trong đó $\text{bit}(i)$ bằng $1$ nếu bit thứ $i$ trong biểu diễn nhị phân của $x$ là $1$, và bằng $0$ nếu ngược lại.

Ví dụ, với $n=4$ và $x=11$ (vì $11=2^0+2^1+2^3$) thì $f(x)=a_0+a_1+a_3$.

Cho thêm một số nguyên $m$. Hãy tìm giá trị lớn nhất của $f(x)$ trên tất cả các $x$ thỏa mãn $0\le x\le m$.

Số $m$ được cho dưới dạng một xâu nhị phân $s_0{s}_1\dots s_{n-1}$ độ dài $n$, trong đó ký tự đầu tiên ứng với bit thấp nhất:

$$m=\sum _{i=0}^{n-1}{s}_i·2^i$$

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ là số phần tử của mảng.
• Dòng thứ hai chứa $n$ số nguyên $a_0,a_1,\dots ,a_{n-1}$.
• Dòng thứ ba chứa xâu nhị phân $s_0{s}_1\dots s_{n-1}$ (không có dấu cách) biểu diễn số $m$.

Dữ liệu ra

• In ra một số nguyên duy nhất là giá trị lớn nhất của $f(x)$ với $0\le x\le m$.

Ràng buộc

• $1\le n\le {10}^5$
• $0\le a_i\le {10}^4$
• $|s|=n$ và $s_i\in \{0,1\}$

Ví dụ