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.awt.geom.Point2D;
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.function.Supplier;

public class Main {
  final static int INF = 1 << 28;
  final static long MOD = 1_000_000_007;
  final static double EPS = 1e-9;
  final static double GOLDEN_RATIO = (1.0 + Math.sqrt(5)) / 2.0;
  Scanner sc = new Scanner(System.in);

  public static void main(String[] args) {
    new Main().run();
  }

  boolean[][][][][][] done;
  int[][][][][][] memo1;
  int[][][][][][] memo2;

  int n, m;
  int[] deck1;
  int[] deck2;
  int[] sum1;
  int[] sum2;
  int[] lastBlock1;
  int[] lastBlock2;
  Flush flush1;
  Flush flush2;

  class Flush {
    TreeMap<Integer, Integer> map = new TreeMap<>();

    void add(int v) {
      if (map.containsKey(v)) {
        map.put(v, map.get(v) + 1);
      } else {
        map.put(v, 1);
      }
    }

    void remove(int v) {
      map.put(v, map.get(v) - 1);
      if (map.get(v) == 0) {
        map.remove(v);
      }
    }

    int floor(int x) {
      return map.floorKey(x);
    }
  }

  Pair<Integer, Integer> dfs(int turn, int index1, int index2, int block1, int block2, int pass) {
    if (pass == 3) {
      return new Pair<>(0, 0);
    }
    // ????????¶?????§?????????????????§?????§?????????
    if (done[turn][pass][index1][index2][block1][block2]) {
      return new Pair<>(
          memo1[turn][pass][index1][index2][block1][block2],
          memo2[turn][pass][index1][index2][block1][block2]
      );
    }
    Pair<Integer, Integer> max;
    if (turn == 0) {
      max = new Pair<>(-INF, INF);
    } else {
      max = new Pair<>(INF, -INF);
    }
    {
      // pass
      flush1.add(index1 - 1);
      flush2.add(index2 - 1);
      Pair<Integer, Integer> ret = dfs(1 - turn, index1, index2, index2 - 1, index1 - 1, pass + 1);
      flush1.remove(index1 - 1);
      flush2.remove(index2 - 1);
      int dokomade1 = Math.max(block2, flush1.floor(index1));
      int dokomade2 = Math.max(block1, flush2.floor(index2));
      if (turn == 0) {
        int p1 = sum1[index1 - 1] - sum1[dokomade1];
        int p2 = sum2[index2 - 1] - sum2[dokomade2];
        ret.f += p1;
        ret.s += p2;
        if (max.f - max.s < ret.f - ret.s) {
          max = ret;
        }
      } else {
        int p1 = sum1[index1 - 1] - sum1[dokomade1];
        int p2 = sum2[index2 - 1] - sum2[dokomade2];
        ret.f += p1;
        ret.s += p2;
        if (max.s - max.f < ret.s - ret.f) {
          max = ret;
        }
      }
    }
    // ??????
    if (turn == 0) {
      if (index1 <= n) {
        Pair<Integer, Integer> ret;
        if (deck1[index1] == -1) {
          ret = dfs(1 - turn, index1 + 1, index2, index2 - 1, block2, 0);
        } else {
          ret = dfs(1 - turn, index1 + 1, index2, block1, block2, 0);
        }
        if (max.f - max.s < ret.f - ret.s) {
          max = ret;
        }
      }
    } else {
      if (index2 <= m) {
        Pair<Integer, Integer> ret;
        if (deck2[index2] == -1) {
          ret = dfs(1 - turn, index1, index2 + 1, block1, index1 - 1, 0);
        } else {
          ret = dfs(1 - turn, index1, index2 + 1, block1, block2, 0);
        }
        if (max.s - max.f < ret.s - ret.f) {
          max = ret;
        }
      }
    }
    done[turn][pass][index1][index2][block1][block2] = true;
    memo1[turn][pass][index1][index2][block1][block2] = max.f;
    memo2[turn][pass][index1][index2][block1][block2] = max.s;
//    debug(turn, index1, index2, block1, block2, pass, max.f, max.s);
    return max;
  }

  void run() {
    n = ni();
    m = ni();
    deck1 = new int[n + 1];
    deck2 = new int[m + 1];
    for (int i = 1; i <= n; ++i) {
      deck1[i] = ni();
    }
    for (int i = 1; i <= m; ++i) {
      deck2[i] = ni();
    }
    lastBlock1 = new int[n + 2];
    {
      int last = 0;
      for (int i = 1; i <= n; ++i) {
        if (deck1[i] == -1) {
          last = i;
        }
        lastBlock1[i] = last;
      }
      lastBlock1[n + 1] = last;
    }
    lastBlock2 = new int[m + 2];
    {
      int last = 0;
      for (int i = 1; i <= m; ++i) {
        if (deck2[i] == -1) {
          last = i;
        }
        lastBlock2[i] = last;
      }
      lastBlock2[m + 1] = last;
    }
    sum1 = new int[n + 1];
    {
      int acm = 0;
      for (int i = 1; i <= n; ++i) {
        if (deck1[i] != -1) {
          acm += deck1[i];
        }
        sum1[i] = acm;
      }
    }
    sum2 = new int[m + 1];
    {
      int acm = 0;
      for (int i = 1; i <= m; ++i) {
        if (deck2[i] != -1) {
          acm += deck2[i];
        }
        sum2[i] = acm;
      }
    }
//    debug("sum1", sum1);
//    debug("sum2", sum2);
//    debug("lastBlock1", lastBlock1);
//    debug("lastBlock2", lastBlock2);
    done = new boolean[2][3][n + 2][m + 2][m + 2][n + 2];
    memo1 = new int[2][3][n + 2][m + 2][m + 2][n + 2];
    memo2 = new int[2][3][n + 2][m + 2][m + 2][n + 2];
    flush1 = new Flush();
    flush2 = new Flush();
    flush1.add(0);
    flush2.add(0);
    Pair<Integer, Integer> ret = dfs(0, 1, 1, 0, 0, 1);
    System.out.println(ret.f - ret.s);
  }

  int ni() {
    return Integer.parseInt(sc.next());
  }

  void debug(Object... os) {
    System.err.println(Arrays.deepToString(os));
  }

  /**
   * ??????????????????????????????
   *
   * @return a ??¨ b ????????§??¬?´???°
   */
  long gcd(long a, long b) {
    if (b == 0) {
      return a;
    }
    return gcd(b, a % b);
  }

  /**
   * ????????????????????????????????????
   *
   * @return mx + ny = gcd(m, n)??¨???????????????(x, y)?????????
   */
  Pair<Long, Long> gcd_ex(long m, long n) {
    long[][] mat = _gcd_ex(m, n);
    return new Pair<>(mat[0][0], mat[0][1]);
  }

  long[][] _gcd_ex(long m, long n) {
    if (n == 0) {
      return new long[][]{{1, 0}, {0, 1}};
    }
    long k = m / n;
    long[][] K = new long[][]{{0, 1}, {1, -k}};
    long[][] r = _gcd_ex(n, m % n);
    long[][] dst = new long[2][2];
    for (int y = 0; y < 2; ++y)
      for (int x = 0; x < 2; ++x)
        for (int i = 0; i < 2; ++i)
          dst[y][x] += r[y][i] * K[i][x];
    return dst;
  }

  /**
   * ??°?????????2???????????¨??????????????????????£?
   *
   * @return a^r (mod 1,000,000,007)
   */
  long pow(long a, long r) {
    long sum = 1;
    while (r > 0) {
      if ((r & 1) == 1) {
        sum *= a;
        sum %= MOD;
      }
      a *= a;
      a %= MOD;
      r >>= 1;
    }
    return sum;
  }

  /**
   * ???????????????
   * O(n)
   *
   * @return {}_nC_r
   */
  long C(int n, int r) {
    long sum = 1;
    for (int i = n; 0 < i; --i) {
      sum *= i;
      sum %= MOD;
    }
    long s = 1;
    for (int i = r; 0 < i; --i) {
      s *= i;
      s %= MOD;
    }
    sum *= pow(s, MOD - 2);
    sum %= MOD;

    long t = 1;
    for (int i = n - r; 0 < i; --i) {
      t *= i;
      t %= MOD;
    }
    sum *= pow(t, MOD - 2);
    sum %= MOD;

    return sum;
  }

  /**
   * ??????????????¢?´¢
   *
   * @param left  ??????
   * @param right ??????
   * @param f     ??¢?´¢????????¢??°
   * @param comp  ??????????????¢??°?????¢?´¢????????¨?????????Comparator.comparingDouble(Double::doubleValue)
   *              ??????????????¢??°?????¢?´¢????????¨?????????Comparator.comparingDouble(Double::doubleValue).reversed()
   * @return ?\?????????§?¨?x
   */
  double goldenSectionSearch(double left, double right, Function<Double, Double> f, Comparator<Double> comp) {
    double c1 = divideInternally(left, right, 1, GOLDEN_RATIO);
    double c2 = divideInternally(left, right, GOLDEN_RATIO, 1);
    double d1 = f.apply(c1);
    double d2 = f.apply(c2);
    while (right - left > 1e-9) {
      if (comp.compare(d1, d2) > 0) {
        right = c2;
        c2 = c1;
        d2 = d1;
        c1 = divideInternally(left, right, 1, GOLDEN_RATIO);
        d1 = f.apply(c1);
      } else {
        left = c1;
        c1 = c2;
        d1 = d2;
        c2 = divideInternally(left, right, GOLDEN_RATIO, 1);
        d2 = f.apply(c2);
      }
    }
    return right;
  }

  /**
   * [a,b]???m:n???????????????????????????
   */
  double divideInternally(double a, double b, double m, double n) {
    return (n * a + m * b) / (m + n);
  }

  /**
   * http://alexbowe.com/popcount-permutations/
   * bit????????£???????????°????°?????????????????????????????????¨???????????????
   * ex)
   * <pre>
   * for (int i = 0; i < 25; ++i) {
   *   int bits = (1 << i) - 1;
   *   long m = C(25, num);
   *   for (j = 0; j < m; ++j) {
   *     ...(25???????????????i???bit????????£?????????)
   *     if (bits != 0)
   *       bits = next_perm(bits);
   *   }
   * }
   * </pre>
   *
   * @param v ?????¨???bit???
   * @return ?¬????bit???
   */
  int next_perm(int v) {
    int t = (v | (v - 1)) + 1;
    return t | ((((t & -t) / (v & -v)) >> 1) - 1);
  }

  /**
   * from http://gihyo.jp/dev/serial/01/geometry part 6
   */
  static class Line {
    double a;
    double b;
    double c;

    /**
     * ?????¬??¢??????????????????????????´??????????????????
     *
     * @param a x????????°
     * @param b y????????°
     * @param c ?????°???
     */
    Line(double a, double b, double c) {
      this.a = a;
      this.b = b;
      this.c = c;
    }

    /**
     * 2???(x1, y1), (x2, y2)???????????´??????????????????
     *
     * @param x1 1?????????x??§?¨?
     * @param y1 1?????????y??§?¨?
     * @param x2 2?????????x??§?¨?
     * @param y2 2?????????y??§?¨?
     * @return ??´???
     */
    static Line fromPoints(double x1, double y1, double x2, double y2) {
      double dx = x2 - x1;
      double dy = y2 - y1;
      return new Line(dy, -dx, dx * y1 - dy * x1);
    }

    /**
     * ?????????????????´?????¨??????????????????
     *
     * @param l ??´???
     * @return ?????????2??´?????????????????´??????null
     */
    Point2D getIntersectionPoint(Line l) {
      double d = a * l.b - l.a * b;
      if (d == 0.0) {
        return null;
      }
      double x = (b * l.c - l.b * c) / d;
      double y = (l.a * c - a * l.c) / d;
      return new Point2D.Double(x, y);
    }

    @Override
    public String toString() {
      return "a = " + a + ", b = " + b + ", c = " + c;
    }
  }

  /**
   * from http://gihyo.jp/dev/serial/01/geometry part 6
   */
  static public class LineSegment {
    double x1;
    double y1;
    double x2;
    double y2;

    LineSegment(double x1, double y1, double x2, double y2) {
      this.x1 = x1;
      this.y1 = y1;
      this.x2 = x2;
      this.y2 = y2;
    }

    Line toLine() {
      return Line.fromPoints(x1, y1, x2, y2);
    }

    boolean intersects(Line l) {
      double t1 = l.a * x1 + l.b * y1 + l.c;
      double t2 = l.a * x2 + l.b * y2 + l.c;
      return t1 * t2 <= 0;
    }

    boolean intersects(LineSegment s) {
      return bothSides(s) && s.bothSides(this);
    }

    // s???????????????????????´????????????????????????????????????
    private boolean bothSides(LineSegment s) {
      double ccw1 = GeomUtils.ccw(x1, y1, s.x1, s.y1, x2, y2);
      double ccw2 = GeomUtils.ccw(x1, y1, s.x2, s.y2, x2, y2);
      if (ccw1 == 0 && ccw2 == 0) { // s??¨?????????????????´?????????????????´???
        // s???????????????1???????????????????????????????????????????????°???s??????????????¨??±?????¨?????????????????§
        // true?????????
        return internal(s.x1, s.y1) || internal(s.x2, s.y2);
      } else { // ????????\????????´???
        // CCW???????¬?????????°????????´??????true?????????
        return ccw1 * ccw2 <= 0;
      }
    }

    // (x, y)?????????????????????????????????????????????????????????
    private boolean internal(double x, double y) {
      // (x, y)????????????????????????????????????????????????????????\?????§????????°????????¨?????????
      return GeomUtils.dot(x1 - x, y1 - y, x2 - x, y2 - y) <= 0;
    }

    public Point2D getIntersectionPoint(Line l) {
      if (!intersects(l)) {
        return null; // ?????????????????´??????null?????????
      }
      return l.getIntersectionPoint(toLine());
    }

    public Point2D getIntersectionPoint(LineSegment s) {
      if (!intersects(s)) {
        return null; // ?????????????????´??????null?????????
      }
      return s.toLine().getIntersectionPoint(toLine());
    }

    @Override
    public String toString() {
      return "(" + x1 + ", " + y1 + ") - (" + x2 + ", " + y2 + ")";
    }
  }

  /**
   * from http://gihyo.jp/dev/serial/01/geometry part 6
   */
  static class GeomUtils {
    static double cross(double x1, double y1, double x2, double y2) {
      return x1 * y2 - x2 * y1;
    }

    static double dot(double x1, double y1, double x2, double y2) {
      return x1 * x2 + y1 * y2;
    }

    // (x1, y1) -> (x2, y2) -> (x3, y3) ??¨?????????????????????????¨????????????´????????£?????????
    // ????¨????????????´???????????????????????´???????????´?????????????????????
    static double ccw(double x1, double y1, double x2, double y2,
                      double x3, double y3) {
      return cross(x2 - x1, y2 - y1, x3 - x2, y3 - y2);
    }

    static double ccw(Point2D p1, Point2D p2, Point2D p3) {
      return ccw(p1.getX(), p1.getY(), p2.getX(), p2.getY(), p3.getX(), p3.getY());
    }
  }

  /**
   * http://qiita.com/p_shiki37/items/65c18f88f4d24b2c528b
   */
  static class FastScanner {
    private final InputStream in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    public FastScanner(InputStream in) {
      this.in = in;
    }

    private static boolean isPrintableChar(int c) {
      return 33 <= c && c <= 126;
    }

    private boolean hasNextByte() {
      if (ptr < buflen) {
        return true;
      } else {
        ptr = 0;
        try {
          buflen = in.read(buffer);
        } catch (IOException e) {
          e.printStackTrace();
        }
        if (buflen <= 0) {
          return false;
        }
      }
      return true;
    }

    private int readByte() {
      if (hasNextByte()) return buffer[ptr++];
      else return -1;
    }

    private void skipUnprintable() {
      while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
    }

    public boolean hasNext() {
      skipUnprintable();
      return hasNextByte();
    }

    public String next() {
      if (!hasNext()) throw new NoSuchElementException();
      StringBuilder sb = new StringBuilder();
      int b = readByte();
      while (isPrintableChar(b)) {
        sb.appendCodePoint(b);
        b = readByte();
      }
      return sb.toString();
    }

    public long nextLong() {
      if (!hasNext()) throw new NoSuchElementException();
      long n = 0;
      boolean minus = false;
      int b = readByte();
      if (b == '-') {
        minus = true;
        b = readByte();
      }
      if (b < '0' || '9' < b) {
        throw new NumberFormatException();
      }
      while (true) {
        if ('0' <= b && b <= '9') {
          n *= 10;
          n += b - '0';
        } else if (b == -1 || !isPrintableChar(b)) {
          return minus ? -n : n;
        } else {
          throw new NumberFormatException();
        }
        b = readByte();
      }
    }
  }

  static class Pair<F extends Comparable<F>, S extends Comparable<S>> implements Comparable<Pair<F, S>> {
    F f;
    S s;

    Pair() {
    }

    Pair(F f, S s) {
      this.f = f;
      this.s = s;
    }

    Pair(Pair<F, S> p) {
      f = p.f;
      s = p.s;
    }

    @Override
    public int compareTo(Pair<F, S> p) {
      if (f.compareTo(p.f) != 0) {
        return f.compareTo(p.f);
      }
      return s.compareTo(p.s);
    }

    @Override
    public int hashCode() {
      return f.hashCode() ^ s.hashCode();
    }

    @Override
    public boolean equals(Object o) {
      if (this == o) {
        return true;
      }
      if (o == null || this.f == null || this.s == null) {
        return false;
      }
      if (this.getClass() != o.getClass()) {
        return false;
      }
      Pair p = (Pair) o;
      return this.f.equals(p.f) && this.s.equals(p.s);
    }

    @Override
    public String toString() {
      return "{" + f.toString() + ", " + s.toString() + "}";
    }
  }

  class BIT<T> {
    int n;
    ArrayList<T> bit;
    BiFunction<T, T, T> bif;

    /**
     * 1-indexed ???Binary Indexed Tree????§??????????
     *
     * @param n   ??????
     * @param bif ?????¨???????????¢??°
     * @param sup ?????????
     */
    BIT(int n, BiFunction<T, T, T> bif, Supplier<T> sup) {
      this.n = n;
      bit = new ArrayList<>(n + 1);
      for (int i = 0; i < n + 1; ++i) {
        bit.add(sup.get());
      }
      this.bif = bif;
    }

    /**
     * i??????????????????v??§??´??°??????
     *
     * @param i index
     * @param v ??°?????????
     */
    void set(int i, T v) {
      for (int x = i; x <= n; x += x & -x) {
        bit.set(x, bif.apply(bit.get(x), v));
      }
    }

    /**
     * ?????¨??????
     *
     * @param defaultValue ?????????
     * @param i            index
     * @return [1, i]?????§f????????¨????????????
     */
    T reduce(T defaultValue, int i) {
      T ret = defaultValue;
      for (int x = i; x > 0; x -= x & -x) {
        ret = bif.apply(ret, bit.get(x));
      }
      return ret;
    }
  }

  class SegmentTree<T> {
    int n;
    ArrayList<T> dat;
    BiFunction<T, T, T> bif;
    Supplier<T> sup;

    /**
     * 0-indexed ???Segment Tree????§??????????
     *
     * @param n_  ????±???????
     * @param bif ?????¨???????????¢??°
     * @param sup ?????????
     */
    SegmentTree(int n_, BiFunction<T, T, T> bif, Supplier<T> sup) {
      n = 1;
      while (n < n_) n *= 2;

      dat = new ArrayList<>(2 * n - 1);
      for (int i = 0; i < 2 * n - 1; ++i) {
        dat.add(sup.get());
      }
      this.bif = bif;
      this.sup = sup;
    }

    /**
     * k??????????????????v??§??´??°??????
     *
     * @param k index
     * @param v ??°?????????
     */
    void set(int k, T v) {
      k += n - 1;
      dat.set(k, v);
      while (k > 0) {
        k = (k - 1) / 2;
        dat.set(k, bif.apply(dat.get(k * 2 + 1), dat.get(k * 2 + 2)));
      }
    }

    /**
     * ?????¨??????
     *
     * @param l ?????????
     * @param r ?????????
     * @return [l, r)??§?????????bif????????¨?????????????????????
     */
    T reduce(int l, int r) {
      return _reduce(l, r, 0, 0, n);
    }

    T _reduce(int a, int b, int k, int l, int r) {
      if (r <= a || b <= l) return sup.get();
      if (a <= l && r <= b) return dat.get(k);
      T vl = _reduce(a, b, k * 2 + 1, l, (l + r) / 2);
      T vr = _reduce(a, b, k * 2 + 2, (l + r) / 2, r);
      return bif.apply(vl, vr);
    }
  }

  class UnionFind {
    int[] par;

    UnionFind(int n) {
      par = new int[n];
      for (int i = 0; i < n; ++i) {
        par[i] = i;
      }
    }

    int find(int x) {
      if (par[x] == x) {
        return x;
      }
      return par[x] = find(x);
    }

    boolean same(int x, int y) {
      return find(x) == find(y);
    }

    void union(int x, int y) {
      x = find(x);
      y = find(y);
      if (x == y) {
        return;
      }
      par[x] = y;
    }
  }
}