B. 宇航员

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

小 A 和小 B 最近玩《宇航员》(一款合作类吃墩桌游)玩上瘾了。《宇航员》里有个任务,描述如下:

小 A 有 n 张牌,第 i 张牌上的点数为 A_i 。小 B 有 m 张牌,第 i 张牌上的点数为 B_i 。每张牌只能出一次。

虽然小 A 可以以任意顺序出牌,但小 A 决定按照发牌时确定好的顺序打牌。当小 A 出了一张牌后,小 B 可以选择出一张牌,但点数必须严格大于小 A 出的牌;或者小 B 也可以不出。

小 A 和小 B 需要合作,使得小 B 出牌的点数总和尽可能大。

遗憾的是,小 A 和小 B 都不知道对方的牌点数是多少,所以不知道要怎么才能达成这个最大值。但你作为旁观者,你能看到二人的手牌,因此他们希望询问你:小 B 出牌的点数总和,最大是多少。

输入格式

第一行,两个整数 n,m,分别表示小 A 和小 B 的牌数。

第二行,n 个整数 A_i ,表示小 A 的牌的点数。同时也代表了 A 发牌时的牌的顺序。

第三行,m 个整数 B_i ,表示小 B 的牌的点数。

输出格式

只有一行,一个整数,表示小 B 出牌的点数总和的最大值。

样例

样例输入 #1

3 4
3 4 7
1 2 4 8

样例输出 #1

12

样例输入 #2

3 3
10 7 8
4 7 6

样例输出 #2

0

样例输入 #3

4 4
4 3 2 1
5 6 7 8

样例输出 #3

26

数据范围与提示

对于 20% 的数据,1≤n,m≤5,1≤ A_i,B_i ≤1000。

对于 40% 的数据,1≤n,m≤1000,1≤ A_i,B_i ≤1000。

对于 70% 的数据,1≤n,m≤ 10^5 , 1≤ A_i,B_i ≤1000。

对于 100% 的数据,1≤n,m≤ 10^5 ,1≤ A_i,B_i 10^9

样例解释1 一种使得小 B 打出的牌总和为 12 的方案如下:

小 A 打出 3,小 B 出 4。

小 A 打出 4,小 B 选择不出。

小 A 打出 7,小 B 出 8。

也有其他方案使得小 B 打出的牌总和为 12。

因为小 A 所有的牌都不小于 1 或 2,所以小 B 只能出 4 或 8。因此 12 是可能的最大值。

样例解释2

因为小 A 所有的牌都不小于小 B 的牌,所以小 B 不可能出牌,总和为 0。

样例解释3

一种使得小 B 打出的牌总和为 26 的方案如下:

小 A 打出 4,小 B 出 5。

小 A 打出 3,小 B 出 6。

小 A 打出 2,小 B 出 7。

小 A 打出 1,小 B 出 8。

也有其他方案使得小 B 打出的牌总和为 26。