#2098. 徐老师的老千计划

徐老师的老千计划

题目描述

马上就要放暑假了!

徐老师把黄老师,石老师,王老师叫到一起打牌,他们决定用打牌的方式选出一个赢家,负责安排暑假所有人的工作内容。

打牌的规则很简单,每个人手里有一些牌,牌上有一些点数,每一轮由徐老师先打出一张牌,然后另外三人可以不出牌,但是要出牌则只能打出点数 严格大于 这张牌的牌,直到徐老师手里打完牌后,游戏结束。

每个人最终的得分由打出的所有牌点数之和决定。

现在石老师和王老师已经打完了自己的所有牌,徐老师还剩下 nn 张牌,黄老师还剩下 mm 张牌

徐老师决定和黄老师私下进行了合作——只要徐老师帮助黄老师成为赢家,那么黄老师就不给徐老师安排任何工作!

现在徐老师想知道,对于剩下的这些牌,怎么出牌可以让黄老师获得尽可能大的得分?

输入格式

第一行包含两个整数 n,mn,m 含义如题

第二行 nn 个整数 AiA_i,表示徐老师手里每张牌的点数

第三行 mm 个整数 BiB_i,表示黄老师手里每张牌的点数

输出格式

输出一行,表示在剩下的这些牌中,黄老师能获得最大的得分

数据范围

测试点编号 1n,m1 \leq n,m \leq 1Ai,Bi1 \leq A_i,B_i \leq
121 \sim 2 55 10001000
343 \sim 4 10001000
575 \sim 7 10510^5
8108 \sim 10 10910^9

样例输入1

3 4
3 4 7
1 2 4 8

样例输出1

12

样例解释1

一种方案为:

  1. 徐老师先打 33,黄老师打 44
  2. 徐老师再打 44,黄老师打 88 最终得分为 4+8=124+8=12

样例输入2

3 3
10 7 8
4 7 6

样例输出2

0

样例解释2

无论徐老师打什么牌,黄老师都没法出牌,得分为 00