Let \(C\) be the count of indices \(i\) with \(A_i+B_i \geq M\). Then \(\displaystyle \sum_{i=1}^N ((A_i+B_i) \bmod M) = \sum_{i=1}^N (A_i+B_i) - CM\). Both \(\displaystyle \sum_{i=1}^N (A_i+B_i)\) and \(M\) are constants solely defined by the input, so it is sufficient to find the rearrangement of \(A\) that maximizes \(C\). From now on, we consider how to maximize \(C\).

The maximum \(C\) can be found greedily as follows:

• Sort \(A\) in descending order, and \(B\) in ascending order.
• For \(k=1,2,\ldots,N\), find the smallest \(B_i\) with \(A_k+B_i \geq M\) among the elements of \(B\) not chosen so far.
• If there is such \(B_i\), match \(A_k\) with \(B_i\).
• The number of matched elements of \(B\) is the maximum possible \(C\).

This greedy algorithm can be implemented using the sliding window technique.

By implementing the algorithm above, the problem can be solved. The computational complexity is \(O(N \log N)\) time per test case.

Sample code (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)