Invisible

Your friend wants to play a card game called "Invisible". The game uses two kinds of cards: scoring cards and interference cards. Each scoring card has a positive value written on it. The rules are as follows.

• The game is played by two players, Player 1 and Player 2. The game starts with Player 1's turn.
• The table has one stack and two decks. The stack is made of the cards that both players have placed. Each player's deck consists of that player's scoring cards and interference cards. A player can check the order of the cards in their own deck or the opponent's deck at any time. At the start of the game, the stack is empty.
• The players take turns. On each turn, a player does exactly one of the following two actions.
  • Place the top card of their own deck on top of the stack. This action cannot be taken if their own deck has no cards.
  • Pass their turn.
• When a player passes, the following processing happens.
  • Each player takes every scoring card in the stack that meets both of these conditions. The taken scoring cards are removed from the table.
    1. The scoring card was placed on the stack by that player.
    2. The card is above every interference card placed by the opponent. (If the stack has no interference card from the opponent, the player takes all scoring cards they placed on the stack.)
  • All cards are removed from the stack.

If both players pass in a row while the stack is empty, the game ends. Each player's final score is the sum of the numbers on the scoring cards that player took.

Each player plays optimally to maximize their own score minus the opponent's score. For the given decks, compute the difference between Player 1's score and Player 2's score when both players play optimally.

The input consists of a single test case in the following format.

n m
a_1 a_2 ... a_n
b_1 b_2 ... b_m

The first line contains the positive integers $n$ and $m$ ($1 \le n, m \le 50$), the sizes of the decks. The second line contains $a_1, a_2, \dots, a_n$, the cards of Player 1's deck from top to bottom. The third line contains $b_1, b_2, \dots, b_m$, the cards of Player 2's deck from top to bottom. Each value is either an integer from 1 to 1,000,000 inclusive or -1. A positive value is a scoring card, and -1 is an interference card.

Print the difference (Player 1's score) minus (Player 2's score) when both players play optimally.