Problem: D --Invisible

Problem Statement

You are trying to play a card game called "Invisible" with your friends. This card game uses two types of cards, a "scoring card" and a "jamming card". A positive value is written on each score card. The rules of this card game are as follows.

* The game is played by two players, player 1 and player 2. The game starts on player 1's turn.
* There is one stack and two decks in the field. The stack consists of cards placed by two players. In addition, the deck possessed by each player consists of the score card and the obstruction card possessed by that player. Players can check the order of cards in themselves or in their opponent's deck at any time. There are no cards on the stack at the beginning of the game.
* The two players alternately perform one of the following two actions exactly once.
* Put the top card of your deck on the top of the stack. However, this action cannot be performed when there are no cards in your deck.
* Pass your turn.
* When the player passes the turn, the following processing is performed.
* Each player gets all the scoring cards in the stack that meet the following two conditions. The score card obtained is removed from the field.
1. This is the score card you put on the stack.
2. Above any disturbing cards placed by your opponent (when there are no disturbing cards in your stack, the player gets all the cards he or she puts on the stack).
* Remove all cards in the stack.



If both players pass in succession with no cards on the stack, the game ends. The final score of each player is the sum of the numbers written on the score card obtained by each player.

Each player takes the best action to maximize the value obtained by subtracting the opponent's score from his own score. Your job is to calculate the difference between Player 1's score and Player 2's score when each player behaves optimally for each player's deck given.

Input

The input consists of a single test case of the form:

$ n $ $ m $
$ a_1 $ $ a_2 $ $ \ dots $ $ a_n $
$ b_1 $ $ b_2 $ $ \ dots $ $ b_m $

The first line consists of positive integers $ n $, $ m $ ($ 1 \ le n, m \ le 50 $) representing the number of decks. The second line consists of $ n $ integers, where $ a_i $ represents the $ i $ th card from the top of player 1's deck ($ 1 \ le i \ le n $). $ a_i $ is more than $ 1 $, less than $ 1 {,} 000 {,} 000 $, or $ -1 $. The third line consists of $ m $ integers, where $ b_j $ represents the $ j $ th card from the top of player 2's deck ($ 1 \ le j \ le m $). $ b_j $ is more than $ 1 $, less than $ 1 {,} 000 {,} 000 $, or $ -1 $. When $ a_i $ and $ b_j $ are positive integers, it represents a scoring card, and when it is $ -1 $, it represents a jamming card.

Output

Output (Score of Player 1)-(Score of Player 2) when each player behaves optimally.

Sample Input 1


twenty two
100 -1
200 300

Output for the Sample Input 1


-100

<image>
<image>
<image>


Sample Input 2


3 5
10 30 -1
-1 90 20 10 -1

Output for the Sample Input 2


0

Sample Input 3


4 5
15 20 10 30
50 30 10 20 25

Output for the Sample Input 3


-60





Example

Input

2 2
100 -1
200 300


Output

-100

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Decimal fixed << setprecision(10)

//int dxy[5] = {0, 1, 0, -1, 0};
// cmd

int table[51][51][101][2][2];

int calc(vi &yui, vi &kyoko, int n, int m, int st, int tu)
{
    bool funami = true, toshino = true;
    int score = 0;

    //cout << "call : " << n << " " << m << " " << st << " " << tu << endl;

    while (st--) {
        if (tu == 0) {
            if (yui[++n] == -1) {
                toshino = false;
            } else if (funami) {
                //cout << "yui : " << yui[n] << endl;
                score += yui[n];
            }
        } else {
            if (kyoko[++m] == -1) {
                funami = false;
            } else if (toshino) {
                //cout << "kyoko : " << kyoko[m] << endl;
                score -= kyoko[m];
            }
        }
        tu = !tu;
    }

    //cout << " " << score << endl;

    return score;
}

int solve(vi &yui, vi &kyoko, int n, int m, int st, int tu, int pa)
{
    if (table[n][m][st][tu][pa] != INF) {
        return table[n][m][st][tu][pa];
    }

    if (tu == 0) {
        int pass_score;
        if (pa == 1) {
            pass_score = 0;
        } else if (pa == 0 && st) {
            pass_score = calc(yui, kyoko, n, m, st, !tu) + 
                solve(yui, kyoko, n, m, 0, !tu, 0);
        } else if (pa == 0 && st == 0) {
            pass_score = solve(yui, kyoko, n, m, 0, !tu, 1);
        }
        int put_score;
        if (n) {
            put_score = solve(yui, kyoko, n-1, m, st+1, !tu, 0);
        } else {
            return table[n][m][st][tu][pa] = pass_score;
        }
        return table[n][m][st][tu][pa] = max(pass_score, put_score);
    } else {
        int pass_score;
        if (pa == 1) {
            pass_score = 0;
        } else if (pa == 0 && st) {
            pass_score = calc(yui, kyoko, n, m, st, !tu) + 
                solve(yui, kyoko, n, m, 0, !tu, 0);
        } else if (pa == 0 && st == 0) {
            pass_score = solve(yui, kyoko, n, m, 0, !tu, 1);
        }
        int put_score;
        if (m) {
            put_score = solve(yui, kyoko, n, m-1, st+1, !tu, 0);
        } else {
            return table[n][m][st][tu][pa] = pass_score;
        }
        return table[n][m][st][tu][pa] = min(pass_score, put_score);
    }
    puts("worning"); return -INF;
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int2(n, m);
    vector<int> yui(n+1);
    for (int i = n; i > 0; i--) {
        cin >> yui[i];
    }
    //Rep(i, n+1) cout << yui[i] << " "; cout << endl;

    vector<int> kyoko(m+1);
    for (int i = m; i > 0; i--) {
        cin >> kyoko[i];
    }
    //Rep(i, m+1) cout << kyoko[i] << " "; cout << endl;

    rep(i, 51) rep(j, 51) rep(k, 101) rep(ii, 2) rep(jj, 2)
        table[i][j][k][ii][jj] = INF;
    
    cout << solve(yui, kyoko, n, m, 0, 0, 0) << endl;
    // a, b, stack, turn(0, 1), pass

    return 0;
}