铁柱和英姬在一个圆环形排列的 $N$ 个格子的棋盘上进行游戏。第 $i$ 个格子上写有一个非负整数 $x_i$。每个格子最多只能放置一枚棋子。

铁柱有 $N$ 枚黑棋，英姬有 $N$ 枚白棋。首先，两人在预先指定的若干格子上放置棋子。之后，由铁柱开始，两人轮流进行回合。在自己的回合中，如果存在与自己已放置的棋子相邻的空格，则选择其中一个格子放置自己的棋子。如果没有这样的格子，则轮到对方的回合。当任何人都无法放置棋子时，游戏结束。

铁柱和英姬都希望最大化自己棋子所在格子的分数之和。给定游戏开始前的棋子布局和每个格子的分数，假设两人都采取最优策略，求出两人最终的得分。

输入格式

第一行包含一个整数 $N$。($3 \leq N \leq 200\,000$)

第二行包含 $N$ 个整数 $c_1, \cdots, c_N$，表示 $N$ 个格子的初始布局，以空格分隔。($0 \leq c_i \leq 2$) 其中 $c_i = 1$ 表示第 $i$ 个格子上有黑棋，$c_i = 2$ 表示第 $i$ 个格子上有白棋，$c_i = 0$ 表示该格子为空。

第三行包含 $N$ 个整数 $x_1, \cdots, x_N$，表示每个格子上的分数，以空格分隔。($0 \leq x_i \leq 10^9$)

输出格式

第一行输出两个整数，分别表示铁柱和英姬最终的得分，以空格分隔。

样例

样例输入 1

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

样例输出 1

12 33

样例输入 2

4
0 0 0 0
6 9 8 8

样例输出 2

0 0

样例输入 3

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

样例输出 3

37 0

样例输入 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

样例输出 4

493 458