题目描述

给你一个长度为 $n$ 的数组 $a$ 和一个长度为 $m$ 的数组 $b$ (所有 $1≤i<m$ 满足 $b_i>b_{i+1}$ )。

最初， $k$ 的值是 $1$ 。你的目标是通过重复执行这两个操作中的一个，使数组 $a$ 为空：

• 类型 1：如果 $k$ 的值小于 $m$ ，且数组 $a$ 不为空，则可以不花费任何代价将 $k$ 的值增加 $1$ 。
• 类型 2：删除数组 $a$ 的一个非空前缀，使得其总和不超过 $b_k$ 。此操作的代价为 $m−k$ 。

求使数组 $a$ 被删除为空的最小总代价。

如果无法通过任何操作序列实现，则输出 $−1$ 。否则，输出操作的最小总代价，以及产生这个最小代价的操作序列的数量对 $10^9+7$ 取模。对于部分子任务，只需要求出最小总代价。

如果在任何一步中选择了不同的操作类型，或者在任何一步中删除的前缀大小不同，那么这两个操作序列就会被认为是不同的。

输入格式

输入包含多组数据。第一行两个整数 $T,f$，表示数据组数和该组数据的子任务信息。

对于每组测试数据，第一行两个正整数 $n,m$，表示数组 $a$ 和 $b$ 的元素数量。

接下来一行 $n$ 个正整数，表示 $a_i$。

接下来一行 $m$ 个正整数，表示 $b_i$。

请注意数据范围中对 $n,m,b_i$ 的限制。

输出格式

对于每组测试数据，如果答案存在，输出一行两个非负整数 $x,y$，分别代表数组 $a$ 被删除为空的最小总代价和 $f \times$ 产生这个最小代价的操作序列的数量对 $10^9+7$ 取模。如果答案不存在，输出 -1。

5 1
4 2
9 3 4 3
11 7
1 2
20
19 18
10 2
2 5 2 1 10 3 2 9 9 6
17 9
10 11
2 2 2 2 2 2 2 2 2 2
20 18 16 14 12 10 8 6 4 2 1
1 6
10
32 16 8 4 2 1

1 3
-1
2 11
10 42
4 1

5 0
4 2
9 3 4 3
11 7
1 2
20
19 18
10 2
2 5 2 1 10 3 2 9 9 6
17 9
10 11
2 2 2 2 2 2 2 2 2 2
20 18 16 14 12 10 8 6 4 2 1
1 6
10
32 16 8 4 2 1

1 0
-1
2 0
10 0
4 0

样例解释

在第一个测试案例中，有 $3$ 个最佳操作序列，产生的总成本为 $1$ ：

• 所有 $3$ 序列都以 $2$ 类型的操作开始，移除前缀 $[9]$ 以生成 $a = [3, 4, 3]$ ，产生的成本为 $1$ 。然后，我们执行 $1$ 类型操作，将 $k$ 的值增加 $1$ （此时 $k = 2$） 。接下来的所有操作都会产生 $0$ 的代价。
• 其中一个序列是先删除前缀 $[3, 4]$ 然后删除 $[3]$ 。
• 另一个序列是先删除前缀 $[3]$ 然后删除 $[4, 3]$ 。
• 另一个序列是先删除前缀 $[3]$ ，然后删除 $[4]$ 和 $[3]$ 。

在第二个测试案例中，不可能删除数组 $a_1 > b_1$ 之后的任何前缀，因此数组 $a$ 不能通过任何操作序列变为空。

数据规模与约定

下发文件

下发文件分别对应子任务 $2$、$4$、$6$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq T \leq 10^3,f \in \{0,1\},1 \leq n,m,n\times m,\sum n \times m \leq 3 \times 10^{5},1 \leq a_i,b_i \leq 10^9,$ 所有 $1≤i<m$ 满足 $b_i>b_{i+1}$。