卡牌游戏 2
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

Momo 和 Jojo 正在进行卡牌游戏。每个卡牌都有一个对应的权值,且相同权值的卡牌最多有两张。游戏由若干回合组成,每个回合分为先手和后手两方,每轮游戏执行以下操作:


  • 先手必须从自己的手牌中选择一张打入牌堆。


  • 后手根据先手打出的卡牌进行响应。


    • 如果后手手牌中存在与先手权值相同的卡牌,则必须打出该卡,并获得卡牌上权值的分数。下一回合的先后手次序不变


    • 如果后手手牌中不存在与先手权值相同的卡牌,则出牌。下一回合的先后手次序交换,即上一回合的先手成为后手,上一回合的后手成为先手。


  • 当一个完整回合结束后,先后手打出的卡牌均进入牌堆中;若任意一方的手牌耗尽,游戏立即结束。


Momo 与 Jojo 均清楚彼此的手牌情况,且在开始时 Momo 先手行动。假设双方均采取最优策略,即在游戏过程中始终以最大化自身得分为目标。请你分别输出 Momo 和 Jojo 在同一局游戏中的最大化得分

输入描述:

第一行输入两个正整数 n,m\ (1 \leq n,m \leq 2 \times 10^5) ,分别代表 Momo 和 Jojo 开局拥有的手牌数。


第二行输入 n 个正整数 a_i\ (1 \leq a_i \leq 10^6) , 分别代表 Momo 的手牌情况。


第三行输入 m 个正整数 b_i\ (1 \leq b_i \leq 10^6) , 分别代表 Jojo 的手牌情况。


数据保证相同权值的卡牌最多有两张


形式化的,对于可重集\{\, x \mid x \in \{a_1, a_2, \dots, a_n\} \cup \{b_1, b_2, \dots, b_m\} \} ,每个 x 在该可重集中的个数不超过 2 个。

输出描述:

一行输出两个正整数,分别代表 Momo 和 Jojo 在同一局游戏中的两人最大化得分

示例1

输入

复制
4 1
1 7 4 6
2

输出

复制
0 0

说明

Momo 出 1,由于 Jojo 没有权值为 1 的牌,所以下一回合 Jojo 先手


Jojo 出 2,由于 Momo 没有权值为 2 的牌,所以下一回合 Momo 先手


由于 Jojo 已经没有手牌了,于是游戏结束,双方得分均为 0

示例2

输入

复制
4 4
10 3 10 1
1 3 6 9

输出

复制
0 4

说明

Momo 出 3,由于 Jojo 有权值为 3 的牌,于是他必须出 3,则 Jojo 得 3 分,所以下一回合 Momo 先手


Momo 出 1,由于 Jojo 有权值为 1 的牌,于是他必须出 1,则 Jojo 得 1 分,所以下一回合 Momo 先手


Momo 出 10,由于 Jojo 没有权值为 10 的牌,所以下一回合 Jojo 先手


Jojo 出 6,由于 Momo 没有权值为 6 的牌,所以下一回合 Momo 先手


Momo 出 10,由于 Jojo 没有权值为 10 的牌,所以下一回合 Jojo 先手


由于 Momo 已经没有手牌了,于是游戏结束,Momo 得 0 分,Jojo得 4 分。