Cheolsu and Younghee are playing a game on a board with $N$ cells arranged in a circle. The $i$-th cell has a non-negative integer $x_i$ written on it. Each cell can hold at most one stone.

Cheolsu has $N$ black stones, and Younghee has $N$ white stones. First, the two players place stones on some predetermined cells. After that, they take turns starting with Cheolsu. On their turn, if there is an empty cell adjacent to a cell where their own stone is already placed, they choose one such empty cell and place their stone there. If no such cell exists, the turn passes to the other player. The game ends when no one can place a stone.

Cheolsu and Younghee each want to maximize the sum of the values of the cells where their stones are placed. Given the initial placement of stones, calculate the final scores of both players assuming both play optimally.

Input

The first line contains $N$. ($3 \leq N \leq 200\,000$)

The second line contains $N$ integers $c_1, \dots, c_N$ representing the initial placement of stones, separated by spaces. ($0 \leq c_i \leq 2$) $c_i = 1$ means a black stone is placed in the $i$-th cell, $c_i = 2$ means a white stone is placed in the $i$-th cell, and $c_i = 0$ means no stone is placed in that cell.

The third line contains $N$ integers $x_1, \dots, x_N$ written on the cells, separated by spaces. ($0 \leq x_i \leq 10^9$)

Output

Print the scores of Cheolsu and Younghee, separated by a space, on the first line.

Examples

Input 1

9
0 1 0 2 0 0 2 0 0
1 2 3 4 5 6 7 8 9

Output 1

12 33

Input 2

4
0 0 0 0
6 9 8 8

Output 2

0 0

Input 3

8
1 0 0 0 0 0 0 1
2 9 4 8 1 8 5 0

Output 3

37 0

Input 4

36
1 1 0 0 2 2 0 1 0 0 0 0 2 0 0 0 1 0 0 0 1 0 0 2 0 0 0 2 0 0 0 1 0 0 0 1
18 23 18 20 40 30 19 15 13 11 19 21 12 25 43 37 23 21 10 4 9 7 3 60 54 32 18 39 42 55 71 92 4 2 40 1

Output 4

493 458