思路
大体上的思路应该和简单版本一致，建议先看本人关于简单版本的题解。
与简单版本不同的是，困难版本的 \(m\) 可以不为 \(1\)，而是取遍 \([1,m]\) 中的整数，所以答案的总值会变大很多倍。
如果直接枚举 \(m\) 次，时间复杂度将会达到 \(O(mn\log n)\) 显然过不了，就算优化排序的复杂度，也是 \(O(mn)\)，还是过不了。
所以需要思考如何优化。
可以发现，无论第一个值取几，很多之前匹配成功的还是能匹配，所以我们考虑先不管 \(a_1\)，把剩下的先匹配了。
因为这里 \(a\) 要少一个，所以我换了个思路，改成了用 \(b\) 匹配 \(a\)，但实际上是一样的，只是我感觉这样写代码要方便一些。
那么，现在来讨论，如果 \(a_1\) 小于没被匹配的最大的 \(b\) 的话，就可以再匹配一个，也就是操作数少一个。
如果 \(a_1\) 大于等于没被匹配的最大的 \(b\) 的话，操作数就会多一个。
假设不算 \(a_1\) 匹配的个数是 \(i\)，没被匹配的最大的 \(b\) 是 \(b_k\) 的话，答案就应该是 \((n-i-1)\times m+\max(0,m-b_k+1)\)。（取 \(\max\) 是因为可能 \(m\) 很小，\(b_k\) 很大，就会导致后面是负的）
AC code
#include<bits/stdc++.h>
using namespace std;
long long T,n,m,a[100005],b[100005],ans,maxn;
int main()
{
scanf("%lld",&T);
while(T--)
{
scanf("%lld%lld",&n,&m),ans=0;
for(long long i=1;i<n;++i) scanf("%lld",&a[i]);
for(long long i=1;i<=n;++i) scanf("%lld",&b[i]);
sort(a+1,a+n),sort(b+1,b+n+1);
long long j=1,flag=0;maxn=0;
for(long long i=1;i<n;++i)
{
while(j<n&&a[i]>=b[j]) maxn=max(maxn,b[j]),++j;
if(j==n)
{
flag=1;
if(a[i]<b[j]) ans=m*(n-i-1)+max(0ll,m-maxn+1);
else ans=m*(n-i)+max(0ll,m-max(maxn,b[j])+1);
break;
}
++j;
}
if(!flag) ans=max(0ll,m-b[n]+1);
printf("%lld\n",ans);
}
return 0;
}