E. Tournament
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

In a distant galaxy, a space football tournament is being held. All $$$2^n$$$ national teams of star systems take part in the competition. The draw has already been made, and the tournament bracket is known: team $$$1$$$ will play against team $$$2$$$, team $$$3$$$ — against team $$$4$$$, and so on. Then the losing teams are eliminated and the winning teams play against each other until all teams but one are eliminated. Each time, pairs are formed from the sequence of winners of the previous round, sorted by their indices in increasing order. In particular, the winner of the game between team $$$1$$$ and team $$$2$$$ faces the winner of the game between team $$$3$$$ and team $$$4$$$, the winner of the game between team $$$5$$$ and team $$$6$$$ faces the winner of the game between team $$$7$$$ and team $$$8$$$, and so on.

Each team is characterized by two values: a game experience value $$$g_i$$$ and a media rating value $$$m_i$$$. The values of $$$g_i$$$ of all teams are pairwise distinct. In every match, the team with the higher experience defeats the team with the lower experience — that is, of course, unless the referee interferes.

The tournament organizers want to sell the rights to broadcast it on TV. However, the TV companies want the tournament to be as media-friendly as possible. The total media rating is calculated as the sum of the ratings of the participants of each game. In other words, if a team plays several games, its media rating is counted the same number of times in the total media rating.

The organizers cannot change the structure of the tournament. However, they know that if the referee is given a "bonus" of $$$d$$$ space dollars, then the referee will "increase" the game experience of the weaker team in the pair by exactly $$$d$$$ units. If the game experience of the weaker team becomes strictly greater than the game experience of the stronger team, then the weaker team wins. Otherwise, the stronger team wins. Note that the game experience of the winning team resets after the match.

The organizers decided to give the referee of each match the same bonus (of course, this bonus should be a non-negative integer amount of space dollars). Your task is to determine the minimum possible bonus that maximizes the total media rating of the tournament.

Input

The first line contains one integer $$$n$$$ ($$$2 \le n \le 8$$$).

The second line contains $$$2^n$$$ integers $$$g_1, g_2, \dots, g_{2^n}$$$ ($$$1 \le g_i \le 10^9$$$) — the game experience values of the teams. All values of $$$g_i$$$ are pairwise distinct.

The third line contains $$$2^n$$$ integers $$$m_1, m_2, \dots, m_{2^n}$$$ ($$$1 \le m_i \le 10^9$$$) — the media rating values of the teams.

Output

Print two integers — the maximum possible total media rating of the tournament and the minimum possible bonus that allows obtaining this rating.

Example
Input
3
10 14 37 22 25 18 20 31
32 19 25 20 21 27 35 30
Output
382
16