AT_tdpc_game ゲーム

[problemUrl]: https://atcoder.jp/contests/tdpc/tasks/tdpc_game すぬけ君とすめけ君がゲームをしている。最初に、二つの山がある。左の山には $A$ 個の物が積まれており、上から $i$ 番目のものの価値は $a_i$ である。右の山には $B$ 個の物が積まれており、上から $i$ 番目のものの価値は $b_i$ である。すぬけ君とすめけ君は、すぬけ君からはじめて交互に次の操作を繰り返す。 - 両方の山が空であれば、ゲームを終了する。 - 片方の山が空であれば、空でないほうの山の一番上のものをとる。 - 両方の山が空でなければ、好きなほうの山を選び、一番上のものをとる。 両者が最善を尽くしたとき、すぬけ君の取るものの価値の合計を求めよ。

入力は以下の形式で標準入力から与えられる。 > $A$ $B$ \ > $a_1 \dots a_A$ \ > $b_1 \dots b_B$

答えを一行に出力せよ。

- $1 \leq A, B \leq 1000$ - $1 \leq a_i, b_i \leq 1000$