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;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll,int> plli;
typedef pair<double, int> pdbi;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
typedef vector<vector<int>> mat;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()

const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const ll INF = 1<<30;
const ll mod = 1000000000 + 7;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;

//#define int long long
#define addm(X, Y) (X) = ((X) + ((Y) % mod) + mod) % mod

int n, m;
int a[55], b[55];
int dp[52][52][52][52][2][2];

int calc(int da, int db, int sa, int sb, int tn) {
    if (sa == 0 && sb == 0) return 0;
    int i = n - 1 - da;
    int j = m - 1 - db;
    bool checka = false, checkb = false;
    int ret = 0;
    if (sb == 0) {
        while (i > (n - 1 - da - sa)) {
            if (a[i] != -1) ret += a[i];
            i--;
        }
        return ret;
    }
    if (sa == 0) {
        while(j > (m - 1 - db - sb)) {
            if (b[j] != -1) ret -= b[j];
            j--;
        }
        return ret;
    }
    //cout << tn << " " << i << " " << n - 1 - da - sa << " " << j << " " << m - 1 - db - sb << endl;
    while (i > (n - 1 - da - sa) && j > (m - 1 - db - sb)) {
        if (tn == 1) {
            if (a[i] == -1) checkb = true;
            else if (!checka) ret += a[i];
            if (b[j] == -1) checka = true;
            else if (!checkb) ret -= b[j];
            i--; j--;
        }
        else {
            if (b[j] == -1) checka = true;
            else if (!checkb) ret -= b[j];
            if (a[i] == -1) checkb = true;
            else if (!checka) ret += a[i];
            i--; j--;
        }
    }
    if (!checka) {
        while (i > (n - 1 - da - sa)) {
            if (a[i] != -1) ret += a[i];
            i--;
        }
    }
    if (!checkb) {
        while (j > (m - 1 - db - sb)) {
            if (b[j] != -1) ret -= b[j];
            j--;
        }
    }
    return ret;
}

int dfs(int da, int db, int sa, int sb, int tn, int cnt) {
    if ((dp[da][db][sa][sb][tn][cnt] != INF) && (dp[da][db][sa][sb][tn][cnt] != -INF)) return dp[da][db][sa][sb][tn][cnt];
    if (da == 0 && db == 0) {
        if (tn == 0) return (dp[da][db][sa][sb][tn][cnt] = max(dp[da][db][sa][sb][tn][cnt], calc(da, db, sa, sb, tn)));
        else return (dp[da][db][sa][sb][tn][cnt] = min(dp[da][db][sa][sb][tn][cnt], calc(da, db, sa, sb, tn)));
    }
    if (da == 0 && tn == 0) {
        if (sa == 0 && sb == 0 && cnt == 1) return (dp[da][db][sa][sb][0][cnt] = max(0, dp[da][db][sa][sb][0][cnt]));
        if (sa == 0 && sb == 0) dp[da][db][sa][sb][0][cnt] = max(dp[da][db][sa][sb][0][cnt], dfs(da, db, 0, 0, 1, 1));
        else dp[da][db][sa][sb][0][cnt] = max(dp[da][db][sa][sb][0][cnt], calc(da, db, sa, sb, tn) + dfs(da, db, 0, 0, 1, 0));
        return dp[da][db][sa][sb][0][cnt];
    }
    else if (db == 0 && tn == 1) {
        if (sa == 0 && sb == 0 && cnt == 1) return (dp[da][db][sa][sb][1][cnt] = min(0, dp[da][db][sa][sb][1][cnt]));
        if (sa == 0 && sb == 0) dp[da][db][sa][sb][1][cnt] = min(dp[da][db][sa][sb][1][cnt], dfs(da, db, 0, 0, 0, 1));
        else dp[da][db][sa][sb][1][cnt] = min(dp[da][db][sa][sb][1][cnt], calc(da, db, sa, sb, tn) + dfs(da, db, 0, 0, 0, 0));
        return dp[da][db][sa][sb][1][cnt];
    }
    if (tn == 0) {
        dp[da][db][sa][sb][0][cnt] = max(dp[da][db][sa][sb][0][cnt], dfs(da - 1, db, sa + 1, sb, 1, 0));
        if (sa == 0 && sb == 0 && cnt == 1) return (dp[da][db][sa][sb][0][cnt] = max(0, dp[da][db][sa][sb][0][cnt]));
        int tmp = calc(da, db, sa, sb, tn);
        if (sa == 0 && sb == 0) dp[da][db][sa][sb][0][cnt] = max(dp[da][db][sa][sb][0][cnt], tmp + dfs(da, db, 0, 0, 1, 1));
        else dp[da][db][sa][sb][0][cnt] = max(dp[da][db][sa][sb][0][cnt], tmp + dfs(da, db, 0, 0, 1, 0));
        return dp[da][db][sa][sb][0][cnt];
    }
    else {
        dp[da][db][sa][sb][1][cnt] = min(dp[da][db][sa][sb][1][cnt], dfs(da, db - 1, sa, sb + 1, 0, 0));
        if (sa == 0 && sb == 0 && cnt == 1) return (dp[da][db][sa][sb][1][cnt] = min(0, dp[da][db][sa][sb][1][cnt]));
        int tmp = calc(da, db, sa, sb, tn);
        if (sa == 0 && sb == 0) dp[da][db][sa][sb][1][cnt] = min(dp[da][db][sa][sb][1][cnt], tmp + dfs(da, db, 0, 0, 0, 1));
        else dp[da][db][sa][sb][1][cnt] = min(dp[da][db][sa][sb][1][cnt], tmp + dfs(da, db, 0, 0, 0, 0));
        return dp[da][db][sa][sb][1][cnt];
    }
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    rep(i, n) cin >> a[i];
    rep(i, m) cin >> b[i];
    rep(i, n + 1)rep(j, m + 1)rep(k, n + 1)rep(l, m + 1)rep(o, 2) {
        dp[i][j][k][l][0][o] = -INF;
        dp[i][j][k][l][1][o] = INF;
    }
    cout << dfs(n, m, 0, 0, 0, 0) << endl;
}