这是这个问题的困难版本。唯一的区别是您还需要输出此版本中的最佳序列的数量。您必须解决这两个版本才能进行破解。
给定一个长度为 $$$n$$$ 的数组 $$$a$$$ 和一个长度为 $$$m$$$ 的数组 $$$b$$$($$$b_i > b_{i+1}$$$ 对于所有 $$$1 \le i < m$$$)。最初,$$$k$$$ 的值为$$$1$$$。您的目标是通过重复执行以下两个操作之一来使数组 $$$a$$$ 为空:
- 输入 $$$1$$$ — 如果 $$$k$$$ 的值小于 $$$m$$$ 并且数组 $$$a$$$ 不为空,则可以将 $$$k$$$ 的值增加 $$$1$$$。这不会产生任何费用。
- 类型 $$$2$$$ - 删除数组 $$$a$$$ 的非空前缀,使其总和不超过 $$$b_k$$$。这会产生 $$$m - k$$$ 的成本。
您需要最小化使数组 $$$a$$$ 为空的操作总成本。如果通过任何操作序列都无法做到这一点,则输出 $$$-1$$$。否则,输出操作的最小总成本,以及产生该最小成本模 $$$10^9 + 7$$$ 的操作序列数。
如果您在任意步骤选择不同类型的操作,或者删除的前缀的大小在任意步骤不同,则两个操作序列被视为不同。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 3 \cdot 10^5$$$, $$$\boldsymbol{1 \le n \cdot m \le 3 \cdot 10^5}$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。
每个测试用例的第三行包含 $$$m$$$ 整数 $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \le b_i \le 10^9$$$)。
对于所有 $$$1 \le i < m$$$,还保证 $$$b_i > b_{i+1}$$$。
保证所有测试用例的 $$$\boldsymbol{n \cdot m}$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,如果可以使 $$$a$$$ 为空,则输出两个整数。第一个应该是操作的最小总成本,第二个应该是实现该最小成本的操作序列的数量,模 $$$10^9 + 7$$$。
如果没有可能的操作序列使 $$$a$$$ 为空,则输出单个整数 $$$-1$$$。
示例
输入 #1
5 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
1 3 -1 2 11 10 42 4 1
注意
在第一个测试用例中,有 $$$3$$$ 最佳操作序列,总成本为 $$$1$$$:
- 所有 $$$3$$$ 序列均以类型 $$$2$$$ 操作开始,删除前缀 $$$[9]$$$ 以使 $$$a = [3, 4, 3]$$$,产生 $$$1$$$ 成本。然后,我们执行 $$$1$$$ 类型操作,将 $$$k$$$ 的值增加 $$$1$$$。所有后续操作现在都会产生 $$$0$$$ 的成本。
- 一个序列通过删除前缀 $$$[3, 4]$$$ 和 $$$[3]$$$ 继续。
- 另一个序列继续删除前缀 $$$[3]$$$,然后删除 $$$[4, 3]$$$。
- 另一个序列继续删除前缀 $$$[3]$$$ 然后 $$$[4]$$$ 然后 $$$[3]$$$。
在第二个测试用例中,从 $$$a_1 > b_1$$$ 开始,不可能删除数组的任何前缀,因此任何操作序列都不能将数组 $$$a$$$ 清空。