C. Confrontation of Numbers
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Two players, Agustín and Brian, play a turn-based game using two arrays of $$$N$$$ integers. Agustín has the array $$$A_1, A_2, \dots, A_N$$$, and Brian has the array $$$B_1, B_2, \dots, B_N$$$.

The state of the game is defined by two variables: a current index $$$x$$$ and a score $$$s$$$, both initially set to $$$0$$$. The players take turns alternately, starting with Agustín. On their turn, a player can perform one of the following two actions:

  • Pass: The player decides not to alter the state of the game.
  • Advance: The player chooses an index $$$y$$$ such that $$$x \lt y \le N$$$. Upon doing so, the current index is updated to $$$x = y$$$, and the score $$$s$$$ is completely replaced: it changes to the value $$$A_y$$$ if it is Agustín's turn, or to the value $$$B_y$$$ if it is Brian's turn.

The game ends immediately when both players decide to pass consecutively. Agustín's goal is to maximize the final value of the score $$$s$$$, while Brian's goal is to minimize it. Your task is to find the final value of $$$s$$$ assuming both players play optimally.

Input

The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 10^{5}$$$), the length of the arrays.

The second line contains $$$N$$$ integers $$$A_1, A_2, \dots, A_N$$$ ($$$-10^{9} \leq A_i \leq 10^{9}$$$), Agustín's array.

The third line contains $$$N$$$ integers $$$B_1, B_2, \dots, B_N$$$ ($$$-10^{9} \leq B_i \leq 10^{9}$$$), Brian's array.

Output

A single integer, the final value of $$$s$$$ when both players play optimally.

Examples
Input
4
5 -2 -2 3
-1 10 4 8
Output
4
Input
1
-5
12
Output
0
Note

In the first example, Agustín chooses $$$x=1$$$, resulting in $$$s=A_1=5$$$. After that, Brian chooses $$$x=3$$$ and $$$s=B_3=4$$$. At that point, Agustín decides to pass, and Brian does as well. These are the optimal moves, and the final score is $$$s = 4$$$.

In the second example, it is optimal for both players to pass.