问题陈述
你要和朋友一起インビジブル玩一种叫做“”的卡牌游戏。 在这个卡牌游戏中,得点カード“和”妨害カード”。 每张记分卡上都写有一个正值。该纸牌游戏的规则如下。
- 游戏由两名玩家(玩家 1 和玩家 2)进行。游戏从玩家 1 的回合开始。
- 游戏中有一堆和两副牌。该叠牌由两名玩家放置的牌组成。此外,每个玩家的牌组由玩家拥有的记分卡和干扰卡组成。玩家可以随时检查自己或对手牌组中的牌的顺序。游戏开始时,牌堆中没有牌。
- 两名玩家轮流执行以下两个动作之一,恰好一次。
- 将你牌库顶牌置于牌堆顶部。然而,如果你的牌组中没有牌,则无法执行此操作。
- 轮到你了。
- 当玩家经过一个回合时,执行以下处理。
- 每位玩家获得堆叠中满足以下两个条件的所有计分卡: 获得的计分卡从游戏中移除。
- 这是您放入堆叠中的记分卡。
- 高于对手放置的所有干扰卡(当堆叠中没有对手干扰卡时,玩家获得他或她放置在堆叠中的所有卡)。
- 从牌堆中取出所有牌。
- 每位玩家获得堆叠中满足以下两个条件的所有计分卡: 获得的计分卡从游戏中移除。
如果两名玩家连续过牌且牌堆上没有牌,则游戏结束。 每个玩家的最终得分是每个玩家记分卡上所写数字的总和。
每个玩家采取最优行动,使自己的分数减去对手的分数所获得的值最大化。 您的任务是根据每个玩家的牌组,计算当每个玩家表现最佳时,玩家 1 的分数和玩家 2 的分数之间的差异。
输入
输入由以下形式的单个测试用例组成:
$n$ $m$
$a_1$ $a_2$ $\点$ $a_n$
$b_1$ $b_2$ $\点$ $b_m$
第一行由正整数 $n$、$m$ ($1 \le n, m \le 50$) 组成,表示这副牌中的牌数。 第二行由 $n$ 个整数组成,其中 $a_i$ 表示玩家 1 牌组顶部的第 $i$ 张牌 ($1 \le i \le n$)。 $a_i$ 大于或等于 $1$ 且小于或等于 $1{,}000{,}000$ 或 $-1$。 第三行由 $m$ 个整数组成,其中 $b_j$ 表示玩家 2 牌组顶部的第 $j$ 张牌 ($1 \le j \le m$)。 $b_j$ 大于或等于 $1$ 且小于或等于 $1{,}000{,}000$ 或 $-1$。 当$a_i$和$b_j$为正整数时,代表记分卡,当$-1$时,代表干扰卡。
输出
当两个玩家都表现最佳时,输出(玩家 1 的得分)-(玩家 2 的得分)。
示例输入 1
2 2 100 -1 200 300
样本输入 1 的输出
-100


示例输入 2
3 5 10 30 -1 -1 90 20 10 -1
样本输入 2 的输出
0
示例输入 3
4 5 15 20 10 30 50 30 10 20 25
样本输入 3 的输出
-60