\(A_i+B_i \geq M\) を満たす \(i\) の個数を \(C\) とすると \(\displaystyle \sum_{i=1}^N ((A_i+B_i) \bmod M) = \sum_{i=1}^N (A_i+B_i) - CM\) が成り立ちます。 \(\displaystyle \sum_{i=1}^N (A_i+B_i)\) と \(M\) は両方入力から定まる定数であるため、 \(C\) の値を最大化するような \(A\) の並び替えを求めれば良いことが分かります。以降は \(C\) の最大化を考えます。

この \(C\) の最大値は以下のような貪欲法で求めることができます：

• \(A\) を降順に、 \(B\) を昇順にソートする。
• \(k=1,2,\ldots,N\) に対し、まだ選ばれていない \(B\) の要素のうち \(A_k+B_i \geq M\) を満たす最小の \(B_i\) を選ぶ。
• そのような \(B_i\) が存在する場合、 \(A_k\) と \(B_i\) をマッチングさせる。
• マッチングされた（選ばれた） \(B\) の要素数が \(C\) の最大値となる。

この貪欲法は尺取り法を用いることで実装することができます。

以上を適切に実装することでこの問題に正答することができます。計算量はテストケース毎に \(O(N \log N)\) 時間です。

実装例(Python3)

for _ in range(int(input())):
    n, m = map(int, input().split())
    a = sorted(list(map(int, input().split())), reverse=True)
    b = sorted(list(map(int, input().split())))
    c, idx = 0, 0
    for v in a:
        while idx < n and b[idx] + v < m:
            idx += 1
        if idx >= n:
            break
        c += 1
        idx += 1
    print(sum(a) + sum(b) - m * c)