Typical DP Contest

B - ゲーム


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 262.144MB

Problem Statement

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

Constraints

  • 1 ≤ A, B ≤ 1000
  • 1 ≤ a_i, b_i ≤ 1000

Input Format

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

Output Format

答えを一行に出力せよ。

Sample Input 1

1 2
1
2 10

Sample Output 1

11
すぬけ君は、最初に左の山の 1 を選ぶべきである。次にすめけ君が右の山の 2 をとり、すぬけ君が右の山の 10 をとる。すぬけ君の取ったものの合計は 1 + 10 = 11 となる。

Sample Input 2

5 5
2 4 5 4 2
2 8 3 4 5

Sample Output 2

21

Submit提出する