D-新田忌赛马_2025年广东工业大学程序设计竞赛月赛（同步赛）

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld

题目描述

本题数据量较大，可能需要使用较快的读入方式。

田忌与齐王再次进行赛马比赛。这次比赛规则有所不同，田忌需要通过合理安排马匹的对阵顺序，最大化自己的赏金收益。

田忌有 $n$ 匹马，第 $i$ 匹马的速度为 $a_i$ ，齐王有 $m$ 匹马，第 $i$ 匹马的速度为 $b_i$ 。由于田忌对自己和齐王的马匹了如指掌，他知道他和齐王的马都是按速度降序排列的。

每次比赛，田忌可以选择自己的一匹从未出战的马 $i$ 与齐王的一匹从未出战的马 $j$ 进行比赛：

你需要计算田忌能够获得的最大赏金总额。

第一行输入两个整数 $n$ 和 $m$ （ $1 \leq n, m \leq 5 \times 10^5$ ），分别表示田忌和齐王的马匹数量。

第二行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$ （ $1 \leq a_i\leq 10^9$ ），表示田忌各匹马的速度。

第三行输入 $m$ 个整数 $b_1, b_2, \ldots, b_m$ （ $1 \leq b_i \leq 10^9$ ），表示齐王各匹马的速度。

保证对 $i \in [1,n-1]$ ，有 $a_{i} \geq a_{i+1}$ ；对 $i \in [1,m-1]$ ，有 $b_{i} \geq b_{i+1}$ 。

输出一个整数，表示田忌能够获得的最大赏金总额。

示例1

复制

2 2
3 1
4 2

复制

示例2

复制

3 3
11 10 7
10 9 8

复制

示例3

复制

6 7
6 5 4 3 2 1
7 6 5 4 3 2 1

复制