← 返回题目列表

AtCoder · tdpc_game

B. 游戏

中文机器翻译题面 查看原题

问题陈述

Snuke君和Sumeke君正在玩游戏。最开始,有两个堆。左边的堆中 A 个物品堆积着,从上面数第 i 个物品的价值是 a_i 。右边的堆中 B 个物品堆积着,从上面数第 i 个物品的价值是 b_i 。Snuke君和Sumeke君由Snuke君先手,交替重复进行以下操作。
  • 如果两堆牌都空了,游戏结束。
  • 如果一堆牌空了,就拿另一堆不为空的牌顶上的牌。
  • 如果两堆牌都不为空,选择喜欢的那一堆,拿最上面的牌。
双方都尽最大努力时,求出Snuke君拿到的牌的总价值。

约束

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

输入格式

输入是按以下格式从标准输入给出的。
A B
a_1 ...a_A
b_1 ... b_B

输出格式

将答案输出到一行中。

示例输入 1

1 2
1
2 10

示例输出 1

11
Snuke君一开始应该选择左边堆中的 1。接着Sumeke君拿右边堆中的 2,Snuke君拿右边堆中的 10。Snuke君拿到的总和是 1 + 10 = 11。

示例输入 2

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

示例输出 2

21