Codeforces Round 982 (Div. 2) |
---|
Finished |
This is the hard version of this problem. The only difference is that you need to also output the number of optimal sequences in this version. You must solve both versions to be able to hack.
You're given an array $$$a$$$ of length $$$n$$$, and an array $$$b$$$ of length $$$m$$$ ($$$b_i > b_{i+1}$$$ for all $$$1 \le i < m$$$). Initially, the value of $$$k$$$ is $$$1$$$. Your aim is to make the array $$$a$$$ empty by performing one of these two operations repeatedly:
You need to minimize the total cost of the operations to make array $$$a$$$ empty. If it's impossible to do this through any sequence of operations, output $$$-1$$$. Otherwise, output the minimum total cost of the operations, and the number of sequences of operations which yield this minimum cost modulo $$$10^9 + 7$$$.
Two sequences of operations are considered different if you choose a different type of operation at any step, or the size of the removed prefix is different at any step.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 3 \cdot 10^5$$$, $$$\boldsymbol{1 \le n \cdot m \le 3 \cdot 10^5}$$$).
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).
The third line of each test case contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \le b_i \le 10^9$$$).
It is also guaranteed that $$$b_i > b_{i+1}$$$ for all $$$1 \le i < m$$$.
It is guaranteed that the sum of $$$\boldsymbol{n \cdot m}$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.
For each test case, if it's possible to make $$$a$$$ empty, then output two integers. The first should be the minimum total cost of the operations, and the second should be the number of sequences of operations which achieve this minimum cost, modulo $$$10^9 + 7$$$.
If there is no possible sequence of operations which makes $$$a$$$ empty, then output a single integer $$$-1$$$.
54 29 3 4 311 71 22019 1810 22 5 2 1 10 3 2 9 9 617 910 112 2 2 2 2 2 2 2 2 220 18 16 14 12 10 8 6 4 2 11 61032 16 8 4 2 1
1 3 -1 2 11 10 42 4 1
In the first test case, there are $$$3$$$ optimal sequences of operations which yield a total cost of $$$1$$$:
In the second test case, it's impossible to remove any prefix of the array since $$$a_1 > b_1$$$, so array $$$a$$$ cannot be made empty by any sequence of operations.
Name |
---|