题目描述

这是问题的困难版本。唯一的区别在于在这个版本中 $m≤10^9$。

你会得到两个整数数组 $a_1,a_2,…,a_n$ 和 $b_1,b_2,…,b_n$。你可以根据需要调整每个数组内元素的顺序。之后，你可以同时执行以下两个操作：

1. 从数组 $a$ 中选择任意一个元素并移除它（所有剩余元素构成新的 $a$ 数组），
2. 从数组 $b$ 中选择任意一个元素并移除它（所有剩余元素构成新的 $b$ 数组）。

令 $k$ 为两个数组的最终大小。使得对于所有的 $1≤i≤k$，都满足 $a_i<b_i$ 的最小操作次数是多少？

这个问题太简单了，所以问题的作者决定增加一些挑战性。我们记原问题是 $(a,b)$ 数组的问题，现在，给你一个正整数 $m$。现在，你需要将原问题求解 $m$ 次，每次的 $a_1$ 有所不同，在第 $i(1≤i≤m)$ 次中：

1. $a[i]_1=i$，
2. $a[i]_j=a_j$，对于 $2≤j≤n$。

你需要求出这 $m$ 次问题的答案的和。

讲人话就是，将简单版的 $a_1$ 从 $1$ 变化到 $m$ 的过程中，所得到的答案的和是多少！

输入格式

每个测试包含多个测试用例。第一行包含一个整数 $t(1≤t≤10^4)$- 输入数据集合的数量。然后是它们的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m(2≤n≤10^5，1≤m≤10^9)$- 数组 $a$ 和 $b$ 的大小以及元素 $a_1$ 的值的上限。

每个测试用例的第二行包含 $n-1$ 个整数 $a_2,…,a_n(1≤a_i≤10^9)$。

每个测试用例的第三行包含 $n$ 个整数 $b_1,b_2,…,b_n(1≤b_i≤10^9)$。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

输出格式

对于每个测试用例，输出所有数组 $(c_i,b)$ 的最小操作总数。

测试样例

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

2
12
16
4

样例说明

在第一个测试案例中：

对于数组对（$a=[1,1]，b=[3,2]$），答案是 0。不需要操作或重新排列元素。

对于数组对（$a=[2,1]，b=[3,2]$），答案是 0。第一个数组的元素可以重新排列为 $[1,2]$。不需要操作。

对于数组对（$a=[3,1]，b=[3,2]$），答案是 1。第一个数组中的元素 3 可以移除，第二个数组中的元素 2 可以移除。

对于数组对（$a=[4,1]，b=[3,2]$），答案是 1。第一个数组中的元素 4 可以移除，第二个数组中的元素 3 可以移除。

在第二个测试案例中： $a[1]=[1,5,1,5],a[2]=[2,5,1,5],a[3]=[3,5,1,5],a[4]=[4,5,1,5],a[5]=[5,5,1,5],a[6]=[6,5,1,5],a[7]=[7,5,1,5]$，$b=[3,8,3,3]$。

$a$ 的七次变化的结果之和为：$1+1+2+2+2+2+2=12$。