The Endspeaker (Hard Version)
Contest: Codeforces Round 982 (Div. 2)
Difficulty rating: 2200
Tags: binary search, data structures, dp, greedy, implementation, two pointers

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:

- Type $$$1$$$ — If the value of $$$k$$$ is less than $$$m$$$ and the array $$$a$$$ is not empty, you can increase the value of $$$k$$$ by $$$1$$$. This does not incur any cost.
- Type $$$2$$$ — You remove a non-empty prefix of array $$$a$$$, such that its sum does not exceed $$$b_k$$$. This incurs a cost of $$$m - k$$$.

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.

Input format:
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$$$.

Output format:
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$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, there are $$$3$$$ optimal sequences of operations which yield a total cost of $$$1$$$:

- All $$$3$$$ sequences begin with a type $$$2$$$ operation, removing the prefix $$$[9]$$$ to make $$$a = [3, 4, 3]$$$, incurring a cost of $$$1$$$. Then, we perform a type $$$1$$$ operation to increase the value of $$$k$$$ by $$$1$$$. All subsequent operations now incur a cost of $$$0$$$.
- One sequence continues by removing the prefixes $$$[3, 4]$$$ then $$$[3]$$$.
- Another sequence continues by removing the prefixes $$$[3]$$$ then $$$[4, 3]$$$.
- Another sequence continues by removing the prefixes $$$[3]$$$ then $$$[4]$$$ then $$$[3]$$$.

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.

Example input:
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

Example output:
1 3
-1
2 11
10 42
4 1

Editorial:
Following on from the editorial for D1. Let's have the $$$\operatorname{dp}$$$ table store a pair of the minimum cost and the number of ways. Since we're now counting the ways, it's not enough just to consider the transition to $$$\operatorname{dp}_{r,j}$$$; we also need to transition to all $$$\operatorname{dp}_{x,j}$$$. Doing this naively is too slow, so let's instead find a way to perform range updates.
Let's say we want to range update $$$\operatorname{dp}_{l,j}, \operatorname{dp}_{l+1,j}, ..., \operatorname{dp}_{r,j}$$$. We'll store some updates in another table at either end of the range. Then, for a fixed value of $$$k$$$ as we iterate through increasing $$$i$$$-values, let's maintain a map of cost to ways. Whenever the number of ways falls to zero, we can remove it from the map. On each iteration, we can set $$$\operatorname{dp}_{i,j}$$$ to the smallest entry in the map, and then perform the transitions. This works in $$$\mathcal{O}(nm \log n)$$$.
Bonus: It's also possible to solve without the $$$\log n$$$ factor. We can use the fact that $$$\operatorname{dp}_{i,k}$$$ is non-increasing for a fixed value of $$$k$$$ to make the range updates non-intersecting by updating a range strictly after the previous iteration. Then we can just update a prefix sum array, instead of using a map.
Alternative solution (with Segment Tree):
Continuing from the dynamic programming solution, let $$$\operatorname{dp}[i][j]$$$ represent the minimum score required to remove all elements after the $$$i$$$-th element, given that the current value of $$$k$$$ is $$$j$$$.
Instead of using a dp table, we maintain $$$m$$$ segment trees, each of length $$$n$$$. The $$$i$$$-th segment tree will represent the $$$i$$$-th column of the dp table.
We precalculate for each $$$i$$$ and $$$j$$$ the furthest position we can remove starting from $$$i$$$ — specifically, the maximum subarray starting from $$$i$$$ with a sum less than $$$b[j]$$$. We store this in $$$\operatorname{nxt}[i][j]$$$. This calculation can be done in $$$\mathcal{O}(nm)$$$ time using a sliding window.
To transition in the dp, we have:
$$$$$$ \operatorname{dp}[i][j] = \min\left( \operatorname{dp}[i][j + 1], \, \min(\operatorname{dp}[i + 1][j], \operatorname{dp}[i + 2][j], \ldots, \operatorname{dp}[\operatorname{nxt}[i][j]][j]) + m - j + 1 \right) $$$$$$
This transition can be computed in $$$\mathcal{O}(\log n)$$$ time thanks to range querying on the segment tree, so our total complexity is $$$\mathcal{O}(nm \log n)$$$.