E-新田忌赛马（加强版）_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$ 进行比赛：

如果田忌的马速度严格大于齐王的马（ $a_i > b_j$ ），田忌将获得 $b_j$ 的赏金。
如果田忌的马速度小于或等于齐王的马（ $a_i \leq b_j$ ），田忌不会获得赏金。

你需要计算田忌能够获得的最大赏金总额，以及有多少种 本质不同 的对阵方案可以获得该最大赏金总额。

两种对阵策略被称为本质不同的，当且仅当其中一个对阵策略中，存在某个田忌的马 $i$ 与齐王的马 $j$ 比赛，而另一个对阵策略中，田忌的马 $i$ 不与齐王的马 $j$ 比赛。

由于对阵策略种类数可能很多，对阵策略种类数只需要计算对 $998244353$ 取模后的答案，但是注意不要对最大赏金总额取模。

注意：你不需要最大化比赛数量，不进行任何比赛也是对阵策略的一种。

输入描述:

第一行输入两个整数 $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}$ 。

输出描述:

输出一行两个整数，第一个整数表示田忌能够获得的最大赏金总额，第二个整数表示有多少种本质不同的对阵策略可以获得该最大赏金总额，其中对阵策略种类需要对 $998244353$ 取模。

示例1

输入

复制

2 2
3 1
4 2

输出

复制

2 2

示例2

输入

复制

3 3
11 10 7
10 9 8

输出

复制

19 2

示例3

输入

复制

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

输出

复制

15 3

示例4

输入

复制

3 3
2 2 2
1 1 1

输出

复制

3 6

示例5

输入

复制

3 3
1 1 1
2 2 2

输出

复制

0 34

示例6

输入

复制

5 8
4 4 2 2 1
6 6 5 4 3 2 1 1

输出

复制

7 20

备注:

在第一个测试用例中，以下两种对阵策略可以取得最大赏金总额。

田忌第一匹马与齐王第二匹马进行比赛，共一场。
田忌第一匹马与齐王第二匹马进行比赛，田忌第二匹马与齐王第一匹马进行比赛，共两场。