You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 1.0 s

Memory Limit: 16.0 MB

In the town of Lumina, there’s a row of N magical lightbulbs set up along the main street. Each lightbulb can be either on or off, and today, the city council wants them all turned off by nightfall to save energy.

To help with this task, you’re given N unique light switches - each with a special power. The i-th switch can toggle the state (on to off or off to on) of all the lightbulbs between positions i and Rᵢ (inclusive). However, using each switch isn’t free; the i-th switch costs Cᵢ coins every time it’s used.

Your job is to figure out the minimum total cost required to ensure that every lightbulb along the row is turned off.

Format

Input

The first line of the input contains a single integer \(N\).

The second line contains a string of lenght \(N\). The \(i^{th}\) character of the string is \(0\) if initially the \(i^{th}\) lightbulb is turned off, and \(1\) if it's turned on.

The third line contains \(N\) integers representing the elements of \(R\).

The fourth line contains \(N\) integers representing the elements of \(C\).

Output

One integer, the required cost. If there is no solution, print \(-1\).

Constraints

• \(1 \le N \le 10^5\)
• \(i \le R_i \le N\)
• \(1 \le C_i \le 19^9\)

Sample

4
1010
2 3 3 4
3 1 2 3

4

5
01100
1 2 3 4 5
1 5 5 2 3

10

4
0101
3 4 3 4
1 1 1 1

2

Explanation

1st Sample

1010: Initial state of the lightbulbs.
1100: After toggling the 2nd switch, changing lightbulbs 2 and 3 (cost 1)
0000: After toggling the 1st switch, changing lightbulbs 1 and 2 (cost 3)

2nd Sample

01100: Initial state of the lightbulbs
00100: After toggling the 2nd switch, changing lightbulb 2 (cost 5).
00000: After toggling the 3rd switch, changing lightbulb 3 (cost 5)

3rd Sample

0101: Initial state of the lightbulbs
0111: After toggling the 3rd switch, changing lightbulb 3 (cost 1)
0000: After toggling the 2nd switch, changing lightbulbs 2, 3, and 4 (cost 1)

Source

CSA - Switch the Lights