Dances (Hard Version)
Contest: Codeforces Round 905 (Div. 3)
Difficulty rating: 1900
Tags: binary search, greedy, sortings, two pointers

This is the hard version of the problem. The only difference is that in this version $$$m \leq 10^9$$$.

You are given two arrays of integers $$$a_1, a_2, \ldots, a_n$$$ and $$$b_1, b_2, \ldots, b_n$$$. Before applying any operations, you can reorder the elements of each array as you wish. Then, in one operation, you will perform both of the following actions, if the arrays are not empty:

- Choose any element from array $$$a$$$ and remove it (all remaining elements are shifted to a new array $$$a$$$),
- Choose any element from array $$$b$$$ and remove it (all remaining elements are shifted to a new array $$$b$$$).

Let $$$k$$$ be the final size of both arrays. You need to find the minimum number of operations required to satisfy $$$a_i < b_i$$$ for all $$$1 \leq i \leq k$$$.

This problem was too easy, so the problem author decided to make it more challenging. You are also given a positive integer $$$m$$$. Now, you need to find the sum of answers to the problem for $$$m$$$ pairs of arrays $$$(c[i], b)$$$, where $$$1 \leq i \leq m$$$. Array $$$c[i]$$$ is obtained from $$$a$$$ as follows:

- $$$c[i]_1 = i$$$,
- $$$c[i]_j = a_j$$$, for $$$2 \leq j \leq n$$$.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) - the number of sets of input data. This is followed by their description.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq m \leq 10^9$$$) - the size of arrays $$$a$$$ and $$$b$$$ and the constraints on the value of element $$$a_1$$$.

The second line of each test case contains $$$n - 1$$$ integers $$$a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, output the total number of minimum operations for all pairs of arrays $$$(c_i, b)$$$.

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

Note:
In the first test case:

- For the pair of arrays $$$([1, 1], [3, 2])$$$, the answer is $$$0$$$. No operations or reordering of elements are needed.
- For the pair of arrays $$$([2, 1], [3, 2])$$$, the answer is $$$0$$$. The elements of the first array can be rearranged to obtain $$$[1, 2)$$$. No operations are needed.
- For the pair of arrays $$$([3, 1], [3, 2])$$$, the answer is $$$1$$$. The element $$$3$$$ can be removed from the first array and the element $$$2$$$ can be removed from the second array.
- For the pair of arrays $$$([4, 1], [3, 2])$$$, the answer is $$$1$$$. The element $$$4$$$ can be removed from the first array and the element $$$3$$$ can be removed from the second array.

Example input:
4
2 4
1
3 2
4 7
5 1 5
3 8 3 3
8 4
4 3 3 2 2 1 1
1 1 1 1 3 3 3 3
9 1
9 2 8 3 7 4 6 5
1 2 3 2 1 4 5 6 5

Example output:
2
12
16
4

Editorial:
Let's learn how to solve the problem for a fixed value of $$$a_1$$$. Notice that we can perform a binary search on the answer. Let's learn how to check if we can remove $$$k$$$ elements from both arrays such that $$$a_i < b_i$$$ holds for the remaining elements. It will be advantageous to sort both arrays, remove the $$$k$$$ largest elements from the first array, and the $$$k$$$ smallest elements from the second array, and then simply check if the condition holds for our pair of arrays. Thus, for a fixed value of $$$a_1$$$, we can solve the problem in $$$O(n \log n)$$$.
Let $$$f(i)$$$ be the answer to the problem for $$$a_1 = i$$$. We make the following observation - there exists a value $$$x$$$ such that: $$$f(1) = f(2) = \ldots = f(x) = f(x + 1) - 1 = f(x + 2) - 1 = \ldots = f(\inf) - 1$$$. Indeed, changing one element of array $$$a$$$ cannot worsen the answer by more than $$$1$$$. Then, we can use binary search to find this value $$$x$$$. The overall complexity is $$$O(n \log n \log m)$$$.