Maximum Sum — Eolymp

Input

The first line contains one integer $n$ ( $1 \leq n \leq 3 \cdot 1 0^{5}$ 1 \le n \le 3 \cdot 10^5) — the length of the string $s$ and the array $a$ .

The second line contains a binary string $s$ of length $n$ . Each character of the string is either $0$ or $1$ .

The third line contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n ( $1 \leq a_{i} \leq 1 0^{9}$ 1 \le a_i \le 10^9).

Output

Output one integer — the maximum possible value of $a_{i} + a_{j}$ a_i + a_j among all pairs of indices $i < j$ i < j such that $s_{i} = 0$ s_i = 0, $s_{j} = 1$ s_j = 1, and $a_{i} < a_{j}$ a_i < a_j.

If no such pair exists, output $- 1$ .

Examples

Example 1

Loading

Example 2

Loading

Note

In the example, you can choose indices $i = 3$ i=3 and $j = 4$ j=4.

For them, $i < j$ i<j, $s_{i} = 0$ s_i=0, $s_{j} = 1$ s_j=1, and $a_{i} < a_{j}$ a_i<a_j hold.

The sum of the corresponding elements is $a_{3} + a_{4} = 3 + 4 = 7$ a_3+a_4=3+4=7.

It is impossible to obtain a larger sum, so the answer is $7$ .

Scoring

Subtask $1$ ( $35$ points): there exists an index $p$ such that $s_{i} = 0$ s_i=0 for all $i \leq p$ i \le p and $s_{i} = 1$ s_i=1 for all $i > p$ i>p.
Subtask $2$ ( $45$ points): $n \leq 1000$ n \le 1000.
Subtask $3$ ( $70$ points): No additional constraints.