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 JAVA):

Solution:
import java.io.*;
import java.util.*;
import java.util.function.Function;

public class Main {

    static int N, M;
    static int[] A, B;

    public static void main(String[] args) {
        FastScanner sc = new FastScanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        A = sc.nextIntArray(N);
        B = sc.nextIntArray(M);

        System.out.println(solve());
    }

    static int solve() {
        return dfs(0, 0, 0, 0, 0, 0, true, 1, new HashMap<>());
    }

    static int dfs(int ai, int bi, int aj, int bj, int as, int bs, boolean first, int pass, Map<Key, Integer> memo) {
        if( pass == 3 ) return 0;

        Key key = new Key(ai, bi, aj, bj, first, pass);
        if( memo.containsKey(key) ) {
            return memo.get(key);
        }

        // カードを山に積む
        int play_point = first ? Integer.MIN_VALUE : Integer.MAX_VALUE;
        if( first ? (ai < N) : (bi < M) ) {
            int nai, nbi, naj, nbj, nas, nbs;
            if( first ) {
                int card = A[ai];
                nai = ai+1;
                nbi = bi;
                if( card == -1 ) {
                    nas = as;
                    naj = aj;
                    nbs = 0; // reset
                    nbj = bi;// reset
                } else {
                    nas = as + card;
                    nbs = bs;
                    naj = aj;
                    nbj = bj;
                }

            } else {
                int card = B[bi];
                nai = ai;
                nbi = bi+1;
                if( card == -1 ) {
                    nas = 0;  // reset
                    naj = ai; // reset
                    nbs = bs;
                    nbj = bj;
                } else {
                    nas = as;
                    naj = aj;
                    nbs = bs + card;
                    nbj = bj;
                }
            }
            play_point = dfs(nai, nbi, naj, nbj, nas, nbs, !first, 0, memo);
        }
        int pass_point = dfs(ai, bi, ai, bi, 0, 0, !first, pass+1, memo) + as - bs;

        int ret = first ? Math.max(play_point, pass_point) : Math.min(play_point, pass_point);
        memo.put(key, ret);
        return ret;
    }

    static class Key {
        int ai, bi, aj, bj;
        boolean first;
        int pass;

        public Key(int ai, int bi, int aj, int bj, boolean first, int pass) {
            this.ai = ai;
            this.bi = bi;
            this.aj = aj;
            this.bj = bj;
            this.first = first;
            this.pass = pass;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Key key = (Key) o;
            return ai == key.ai &&
                    bi == key.bi &&
                    aj == key.aj &&
                    bj == key.bj &&
                    first == key.first &&
                    pass == key.pass;
        }

        @Override
        public int hashCode() {
            return Objects.hash(ai, bi, aj, bj, first, pass);
        }
    }

    @SuppressWarnings("unused")
    static class FastScanner {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

        String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken("\n");
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        int[] nextIntArray(int n, int delta) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt() + delta;
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }

    static <A> void writeLines(A[] as, Function<A, String> f) {
        PrintWriter pw = new PrintWriter(System.out);
        for (A a : as) {
            pw.println(f.apply(a));
        }
        pw.flush();
    }

    static void writeLines(int[] as) {
        PrintWriter pw = new PrintWriter(System.out);
        for (int a : as) pw.println(a);
        pw.flush();
    }

    static void writeLines(long[] as) {
        PrintWriter pw = new PrintWriter(System.out);
        for (long a : as) pw.println(a);
        pw.flush();
    }

    static int max(int... as) {
        int max = Integer.MIN_VALUE;
        for (int a : as) max = Math.max(a, max);
        return max;
    }

    static int min(int... as) {
        int min = Integer.MAX_VALUE;
        for (int a : as) min = Math.min(a, min);
        return min;
    }

    static void debug(Object... args) {
        StringJoiner j = new StringJoiner(" ");
        for (Object arg : args) {
            if (arg instanceof int[]) j.add(Arrays.toString((int[]) arg));
            else if (arg instanceof long[]) j.add(Arrays.toString((long[]) arg));
            else if (arg instanceof double[]) j.add(Arrays.toString((double[]) arg));
            else if (arg instanceof Object[]) j.add(Arrays.toString((Object[]) arg));
            else j.add(arg.toString());
        }
        System.err.println(j.toString());
    }
}